# Gödel's Proof as a proof strategy for P = NP or P != NP

I have had this thought for quite a while. Gödel proved the incompleteness of arithmetic by creating a one-to-one correspondence with a number and certain numerical relationships to create a statement that says, in effect, "I cannot be proven."

My question is: has there been any attempt to go the other direction? That is, has anyone succeeded in showing that an arbitrary statement -- such as P=NP -- Is a statement that says of itself that it has no proof? In order for this to happen, a one-to-one relationship needs to be shown between what that means in the mathematics of it and its "meta meaning". In short, Gödel went from meta-meaning ("this statement cannot be proven") and constructed a number that, in effect, stated this meta-meaning. Has there been attempts to show that statements already in existence have a meta meaning stating that they cannot be proven? if so, has anybody used this strategy to prove or disprove P=NP's provability? It may be a simple question, but it has been bothering me for a while. Thanks for reading :)

-
Scott Aaronsons survey might be interesting: scottaaronson.com/papers/pnp.pdf. –  Mike B. Nov 16 '11 at 15:54

My thoughts on the subject, which must be taken with a grain of salt as I'm far from being an expert on this subject (or any subject, to that matter):

This idea was mentioned in Douglas Hofstadter's "Godel, Escher, Bach", but I never saw it seriously discussed. As far as I know, no independence proof (e.g. the independence of the Continuum hypothesis) has ever used such a technique, and it's hard to see why P=NP will be different.

It is worth remembering that Godel's statement is difficult to build. In effect, you can think of it as a logical encoding of a small computer program which knows how to decode Godel's numbering and knows how to check proofs (in an effective system, i.e. one in which proof checking is computable), and to top it all, it also contains an encoding of itself using a smart diagonalization trick. This is not something you stumble upon; it is a very delicate construct.

I see no reason to assume that a statement such as P=NP, which deals with a class of Turing machines, can be re-interpreted as discussing itself. If such a far-fetched interpretation can be made for P=NP, why can't it also be done for, say, IP=PSPACE (which is well known to be true)?

So although this idea is quite fascinating, I see no reason to believe it is true; however, it might be explored by taking some toy independent statements and trying to see if they can be re-interpreted in a way they talk about themselves (I think it will already prove immensely difficult because of the complexity of making a statement talk about itself). I would start there, not attack P=NP directly.

It is also worth mentioning that there is no apparent reason why P=NP is undecidable. There are many indications that it is undecidable using standard methods (e.g. diagonalization - see Baker-Gill-Solovay) but many other complexity-theory problems had a similar difficulties and were laid to rest using a clever new formulation or point of view (IP=PSPACE being a nice example).

-
+1 Your answer is insightful. But isn't the problem of P vs. NP in NP itself (the answer to be problem being verifiable in polynomial time)? Isn't that a form of self reference? –  djhaskin987 Nov 16 '11 at 16:10
No; P vs NP is a question about LANGUAGES, while "the P vs NP question" is only a WORD (in a language like "all the statements in the language of ZFC which are true in the Natural numbers"). More specifically, there IS a Turing machine which answers the question "is P=NP?" in polynomial time - either the one that answers "yes" or the one that answers "no". So the P vs NP problem does not really discuss itself. –  Gadi A Nov 16 '11 at 16:14

In fact, a distant relative of the concept you suggest has been applied to a question of complexity; as Gadi alludes to briefly in a comment, while Peano Arithmetic (the theory of addition and multiplication over the natural numbers) is incomplete (this is the core of Godel's theorem), Presburger Arithmetic - the theory of only addition over the natural numbers - is decidable, but it's hard: it requires doubly-exponential time. It turns out that this can be proved via a version of Godel's proof; the key is that multiplication can be 'approximated' in the theory of addition, up to a certain level:

For each natural number $k$ there is a formula $M_k(x,y,z)$ of length $O(k)$ in the language of addition such that $M_k$ is true if $x\times y = z$ and $\displaystyle{x\lt 2^{2^{2k}}}$.

This implies that if the theory of addition were decidable without using exponentially large numbers, then the theory of addition and multiplication (i.e., Peano Arithmetic) would also be decidable - essentially, the constructions of Godel's proof would go through using the additive approximation to multiplication to build a Godel sentence. Since we know the conclusion is false, the hypothesis must also be, and the theory of addition is exponentially hard. This is laid out in Paul Young's paper "Godel theorems, exponential difficulty and undecidability of arithmetic theories: an exposition" in the Recursion Theory collection; you can find most of the paper on Google Books.

-

This question is fundamentally misinterpreting Godel's theorem. As far as we know, there is not a single "unprovable theorem", all theorems should be provable if they are meaningful, and provable in a natural system of mathematics, extending arithmetic with appropriate higher infinity axioms.

The objects constructed by Godel's theorem are unprovable in a given axiomatic system only, their natural function is as new axioms, which strengthen the axiom system in ways that allow them to be proven. Within set theory, you use axioms of higher infinity (inaccessible cardinals of various types) to do this.

Godel's theorem explains why you need these stronger axioms, and why these axioms produce new true theorems about arithmetic (although such enormously infinite objects are not particularly absolute themselves). But it does not mean that there is any question whatsoever that is undecidable in the sense of this question. In particular, the idea that P!=NP could be "undecidable" is not reasonable.

But P!=NP is not a simple statement, it says that there does not exist a computer program such that for any instance of 3SAT, it halts, and the eventual output satisfies this instance three sat. The structure of this statement is (not)(exists)(forall)(exists), or (forall)(exists)(forall), and this is Pi-3 (meaning three alternating quantifiers, starting with forall), and any true Pi-3 statement is hard to prove.

[ EDIT: Kaveh points out below that the innermost quantification is fake--- you don't need to do a quantification to check when a program in P halts--- it is guaranteed to halt in polynomial time. So if you phrase it properly, including the order n of the polynomial running time in the outermost "there exists", the innermost quantification is bounded above, and so it doesn't count as a step up. The proper statement: For all programs R and integers n such that R(p) stops changing in time less than $p^n$, there exists an instance of SAT indexed by integer P, such that the output of R(P) after Pn steps is not a solution to P. The proper phrasing shows that this is a $\Pi_2$ statement, not $\Pi_3$. $\Pi_2$ statements are not as difficult.]

The statement that every theorem should be provable from an axiom of higher infinity is not a theorem--- it is difficult to even formulate the statement precisely, because it it refers to a process of higher-infinity which cannot be formalized completely within an axiom system. But this is an article of mathematical faith--- articulated by Cohen in "Set Theory and the Continuum Hyptothesis". You might want to restrict this article of faith to Pi-1 statements, to statment

For a better discussion, see this: http://mathoverflow.net/questions/72062/what-are-some-proofs-of-godels-theorem-which-are-essentially-different-from-th/72151#72151

-
It can be state as a $\Pi_2$ statement: $\forall M\in \mathsf{P} \ \exists n \in \mathbb{N} \ \big( M(n) \neq SAT(n) \big)$. –  Kaveh Nov 21 '11 at 1:41
@Kaveh: I see, thanks. Fixed. –  Ron Maimon Dec 18 '11 at 11:42

It has been shown that P=NP( or P != NP) cannot be proved by diagonalization, using diagonalization. The proof of this relies on giving an oracle to a Turing Machine. See the references below:

http://courses.csail.mit.edu/6.841/spring09/scribe/lect02.pdf

http://www.chronon.org/articles/PvNP.html

-
What does does diagonalization have to do with Godel's Proof? I ask sincerely, it interests me :). –  djhaskin987 Dec 7 '11 at 16:02
The story line of "diagonalization" can be traced back to Cantor, who proved [0,1] is uncountable, then Godel, who proved his famous incompleteness theorem, and Turing, who proved the undecidable halting problem. So it is natural for people to see if same trick can be used to tackle P=NP. Unfortunately, it is not. –  FiniteA Dec 8 '11 at 3:47
I am not familiar with Godel's proof. But I think the link may provide the connection: thalesianfools.blogspot.com/2007/04/… or this link in wiki en.wikipedia.org/wiki/Diagonal_lemma –  FiniteA Dec 8 '11 at 3:49
By the way, the "story line of diagonalization" mentioned above is taken from Roger Penrose's Emperor's New Mind, if I remember correctly. –  FiniteA Dec 8 '11 at 3:59

I am far from an expert also, but every independent statement can be interpreted as saying 'I am not provable', thats what it means to be undecidable. And every theorem says 'I am provable'.

-
Interpreted - how? Here "interpretation" has a formal meaning, not an everyday one. Can you give a concrete example of such a statement and interpretation? –  Gadi A Nov 16 '11 at 16:20
Con(T), (Con(T) and 2+3=5) –  100101011011010011010110101110 Nov 16 '11 at 16:21
I am not sure how this statement says something about itself. –  Gadi A Nov 16 '11 at 16:26
This is incorrect in two different ways. First, it doesn't apply to every formal system; there are conditions needed which can be quite delicate (Presburger arithmetic is a good example of just how delicate they are). Second, for every suitable formal system there is a corresponding Godel statement; there isn't one Godel statement which applies to all the formal systems. That being said, I fail to see how your comment was relevant to mine. –  Gadi A Nov 16 '11 at 16:41
-1: The correct statement is that the proof every theorem in a formal system is trivially a proof that the theorem is provable. But a proof that a theorem is unprovable does not guarantee that the theorem is equivalent to its own unprovability. To see an example, consider TWEEDLEDEE and TWEEDLEDUM in this answer: mathoverflow.net/questions/72062/… . Neither is provable, but neither states that it itself is unprovable (rather each states that the other is). –  Ron Maimon Nov 16 '11 at 19:50