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?

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestThe four color theorem, perhaps?

Log in to reply

Yes, that came to my mind too

Log in to reply