]]>“I confess indeed that Fermat’s theorem as an isolated proposition has little interest for me, since a multitude of such propositions, which one can neither prove nor refute, can easily be formulated.”

Nowadays we can extend Gauss’ intuition by exhibiting Turing machines in P that recognize languages that are lists of such propositions. Lists of mortal/immortal matrices are natural candidates for such languages.

It is easy to specify Turing machines in P that generate ordered lists of provably mortal matrices, together with a certificate of each matrix’s mortality. Conversely (but less rigorously) we can conceive a class of Turing machines, each of which guesses a list of

immortalmatrices (on probablistic grounds) such that most of those Turing machines recognize (in P!) matrix languages whoseimmortalityis Gödel-undecidable.The intuition here is the Complexity Zoo’s inhabitants may generically include wild languages that are recognized in P and whose words assert true statements that are Gödel-undecidable—yet not provably so. And the point is that these wild languages in P (if they exist?) are intimately associated to complexity-theoretic questions that are subtle, open, and difficult.

An essay clarifying these “wildness-in-P” issues would be very welcome to me and many! ðŸ™‚

Currently, *all* the statements that are proven to independent of ZF set theory involve either transfinite sets or Gödelian self-reference. (There are relatively “natural” mathematical statements, like the Paris-Harrington theorem, that are provably independent of *Peano Arithmetic*, but those statements *are* provable in stronger theories like ZF set theory.)

*Logically*, we can’t exclude the possibility that “normal” mathematical statements, like (say) Goldbach’s Conjecture, are independent as well and could even be proved to be independent. Such statements would still be either true or false; it’s just that our current axioms wouldn’t suffice to say which! Indeed, as you correctly pointed out, if Goldbach’s Conjecture is false then it has a finite counterexample, which means that if it’s independent of ZF set theory then it’s metatheoretically *true*!

On the other hand, logically it’s possible that Goldbach would be independent of ZF, and that fact *itself* would be unprovable in ZF, and so on ad infinitum. In that case, even though Goldbach would be true, it’s not clear how we could ever come to know that.

But such possibilities seem very unlikely given our actual experience. As I said, my guess is that the lack of a proof of Goldbach’s Conjecture reflects the current limitations of human intelligence rather than the ultimate limitations of ZF set theory.

]]>I’m intrigued by the statement that you are “>99%” sure that Goldbach’s conjecture has a finite proof. Is there any yes/no question in mathematics that does not have a finite proof? (and I mean a single yes/no question, not a problem with a family of instances that can be undecidable.) Is this what the incompleteness theorem answers? Do we have a concrete example of such a problem? (I’m familiar with statements of the type: “G: G is not provable”. So, let’s exclude self-reference.)

Wouldn’t it also be the case that if Goldbach conjecture did not have a finite proof, then it would necessarily be true? (Because if it was false, it would have a finite proof: just the counterexample.)

]]>(1) Yes, there’s an important result called “the equivalence of search and decision” for NP-complete problems, traditionally given as a homework problem in theory courses. It says that, if you have a polynomial-time algorithm to *decide* whether (say) a 3SAT formula φ(x_{1},…,x_{n}) is satisfiable or not, then you can convert it into a polynomial-time algorithm to *find* a satisfying assignment if one exists. I’ll give you a hint: first you run your decision algorithm on the (n-1)-variable formula

φ_{0}(x_{2},…,x_{n}) := φ(FALSE,x_{2},…,x_{n}).

then you run it on

φ_{1}(x_{2},…,x_{n}) := φ(TRUE,x_{2},…,x_{n}),

Then you … OK, the rest is homework for you. ðŸ˜‰

On top of the above, any standard reduction from the Goldbach problem to 3SAT will have the further property of being a *witness mapping*. That is, in polynomial time, you can *directly* convert any n-symbol ZF proof of Goldbach’s Conjecture into a satisfying assignment of the 3SAT formula, and vice versa.

(2) Yes, the shortest ZF proof of Goldbach’s Conjecture (assuming such a proof exists, which I’m >99% sure of!) has some fixed, finite length n*. But this is only an issue for Gödel’s argument in the same way asymptotics are *always and everywhere* an issue for complexity theory! It’s clear that a polynomial-time algorithm will “eventually” win massively over an exponential-time one. So the sole remaining question is whether it will “start winning soon enough”—i.e., on those instances that we finite creatures actually want to solve. GP of size n* is just one example of such an instance (albeit one with the interesting feature that we don’t yet know n*).

Let’s call the decision problem you have stated above “GP” (for Goldbach’s proof). I agree that we can give a poly length reduction from GP to 3SAT (I’m guessing it would go as GP YES iff 3SAT satisfiable). But let’s say the answer to GP is YES for some n=n*. When we solve the associated 3SAT instance, do we just get to know that the answer to GP_n* is YES, or do we also get a proof of Goldbach’s conjecture? I guess my question is: (i) Is there some argument that says if you can give the correct YES/NO answer to 3SAT in poly time, then with polynomially more work, you can also find a satisfying instance? and (ii) Will the reduction work in a way that a satisfying assignment would directly translate into a proof of Goldbach?

My only comment is that the argument for P=NP having consequences for (efficiently) solving Goldbach still needs a little fix. Indeed, Goldbach has a proof of some finite length n*. (It does BTW, right?) The reduction then turns GP_n* into a 3SAT of length n**. It could happen that even if P=NP, the best poly time algorithm for 3SAT has running time much larger than 2^n** on the instances of size n**. (In other words, we can’t give the usual “asymptotic” argument for why poly time is better than exp time since GP is only interesting up to n*.)

BTW, it’s amusing to think that we can turn the P vs. NP question into solving essentially a single instance of 3SAT. Maybe people should try that approach ðŸ˜‰

]]>- “Given an input n, decide whether Goldbach’s conjecture has a ZF proof with n symbols or fewer”

is an NP problem (and hence reducible to 3SAT, by the Cook-Levin Theorem). So if you had a polynomial-time algorithm for 3SAT, then it would also be a P problem.

That would mean that, however long the shortest ZF proof of Goldbach’s Conjecture turned out to be, you could *find* that proof after a number of steps that was only polynomially greater than the number of steps you’d need to write the proof down.

(Except for the part about 3SAT and the Cook-Levin Theorem, the above argument is essentially the one that Gödel made in his 1956 letter to von Neumann.)

]]>Quick question: what is the argument behind the statement that if P was equal to NP, then we could (efficiently) solve all the Clay Institute problems? Could you please make that more precise?

To make things more concrete and perhaps simpler, let’s take e.g. the (< $1M) Goldbach conjecture. If I have a polynomial time algorithm for 3SAT, how can I solve Goldbach?

(I'm guessing that one would argue that the Goldbach conjecture should have a proof that is easily recognizable; so it's in NP, and therefore if P=NP, the proof should be easy to find. But how do we even phrase the Goldbach conjecture, which is just one instance of a problem as a family of problems with a well defined "input" and "input size"? And once we have done that, how do we show it's in NP?)

]]>Hartmanis’ monograph argues that (what we would today call) relativization theorems are compatible (obviously) with nondecidability of PvsNP … and thus constitute (less obviously?) heuristic evidence of it … and even (potentially?) an avenue for proving it.

Of course, the distillation of concrete open problems from discussions like Hartmanis’ is a notoriously subtle task. Even with the help of decades of hindsight, it was not easy for Gödel, Church, and Turing to appreciate that the open problems associated to Hilbert’s second question (of 1900) encompassed not only consistency but decidability … and Hilbert himself was slow to appreciate this avenue of research.

Similarly, even with the help of decades of hindsight, it is by no means obvious (to me at least) what worthy open problems might be distilled from Hartmanis’ 1978 monograph … but the decidability of the separation between P and NP surely is one of them.

]]>