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?

Note by Agnishom Chattopadhyay
6 months, 2 weeks ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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} \)

Comments

Sort by:

Top Newest

The four color theorem, perhaps?

Nick Turtle - 6 months, 1 week ago

Log in to reply

Yes, that came to my mind too

Agnishom Chattopadhyay Staff - 6 months, 1 week ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...