# On Alien Truths

I had been discussing some problem with a friend a few months back, and we stumbled upon a way to solve that problem that involves a lot of computation, and we had a conversation about how some statements cannot really have elegant proofs.

I discovered that that month's issue of ACM Communications talked about this idea, which they called Alien Truths. And furthermore, I found some evidence from formal logic embracing this idea: namely Godel's Speedup Theorem, which says (to quote wikipedia):

there are theorems whose proofs can be drastically shortened by working in more powerful axiomatic systems.

I attach a couple of emails below

Hi;

We had a conversation last Monday about how I believe that not all problems have elegant solutions, as a comment on the problem of inverting Hilbert Matrices. I recently found some interesting material related to that view.

In the August Issue of Communications of the ACM, a concept called Alien Truth has been discussed (see pg 8 of the pdf version, here). They define it as something like this:

> [...] a truth statement is alien if humanly understandable case-splits are way too big for any plain brute-force method, but there exists a giant case-split that mysteriously avoids an enormous exponential effort.

And I found a relevant Wikipedia Article too: Godel's Speedup Theorem

--Agnishom

This was the Boolean Pythagorean triples problem:

> [...] if it is possible to color each of the positive integers either red or blue, so that no Pythagorean triple of integers a, b, c, [...] are all of the same color.

And you could find the link to the pdf of the article in this attached email.

--Agnishom

P.S: Look at page 22 of this document for some practical uses of SAT solvers. (Because apparently Boolean Pythagorean Triples was not practical enough.)

What are some problems you know you wish had more elegant proofs?

3 months, 3 weeks ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

The four color theorem, perhaps?

- 3 months, 2 weeks ago

Yes, that came to my mind too

Staff - 3 months, 1 week ago