Deceptively simple math conjectures Why is it that some mathematical problems with seemingly simple statements end up soliciting extremely complicated and groundbreaking proofs or remain unsolved for extended periods of time? (Ex. Collatz conjecture, FLT, Twin prime conjecture, abc conjecture, Legendre's conjecture, etc.) Do they share anything in common?
 A: I'm not sure how to answer "Do they share anything in common?" But here's a reason why we'll always find simple conjectures with surprisingly long proofs:
Godel's incompleteness theorem says (among other things) that the set of sentences which can be proved by a fixed "reasonable" set of axioms is never computable. That is, as long as $T$ is a "reasonable" set of axioms, there is no computer program that when fed a sentence $\varphi$ will output "Yes" iff $\varphi$ is a theorem of $T$, and "No" iff $\varphi$ is not a theorem of $T$.
This has an important corollary for the lengths of proofs. Fix some axiom system - say, Peano Arithmetic. Then I claim:

There is no computable function $f$ such that any sentence of length $n$ which is provable in $PA$ has a proof of length at most $f(n)$.

Why? Well, otherwise let $f$ be such a function; to tell if $PA$ proves some sentence $\varphi$, just search through all (finitely many) proofs of length $\le f(\vert\varphi\vert)$. If you don't find one, then $\varphi$ is not a theorem of $PA$!
This means we will always see "surprisingly long" proofs: for example, there will be some theorem of $PA$ which when written down is $n$ characters long, but whose shortest proof in $PA$ has length $$n^{n^{n^{...}}}\quad\mbox{($n^{100000}$-many times)}.$$ Of course, this says nothing$^*$ about how to find such surprisingly hard-to-prove theorems, especially natural examples of same. A kind of mathematical optimism (well, I think it's optimism :P) says that we should always expect natural examples of all possible logical phenomena, but that's not a theorem, that's an opinion (and maybe a silly one at that :P).

$^*$Actually we can effectively generate such examples. But they're really artificial.
