What's wrong with this proof that P = NP?
in [Theory]
|
Prev: Approximate/Fuzzy Search for strings keys
Next: Call For Participation: WORLDCOMP'08 (CS and CE conferences), July 14-17, 2008, Las Vegas
From: cplxphil on 20 Jun 2008 21:21 Hello, I have noticed that there seem to be an abundance of people who have published false proofs that P equals, or does not equal, NP. I have been working for some time to generate my own proof that P != NP; however, after coming up with my proof, I am realistic enough to realize that it may very well be wrong. In that spirit, I would prefer not to declare, "I have proved P != NP!!!!," but rather to ask if anyone can find anything wrong with the proof that I have come up with. I cannot find anything wrong with my proof, but I am suspicious of it for two reasons: 1) It uses diagonalization, and according to Baker-Gill-Solovay, that is not a likely approach. I have tried to address my use of diagonalization in the full version of the proof (not posted) and I have tried to reconcile it with B-G-S, but I am not sure if I am right. 2) After looking at the completed proof ("proof"?), I thought that by using the same logic I could prove that valid proof generation might not even be in NP, using the logic that I came up with. That, according to what I have read, is not accurate. So again...I am a mathematics major at a college (in Virginia, if you're curious), but I do not have any formal training in complexity theory, making me an amateur. I submit the following proof with the question, "What's wrong with it?" Please don't hesitate to e-mail me at cplxphil(a)gmail.com. Also, note that this is the abridged, informal version of the proof...I have simplified a few concepts. If anyone objects to those simplifications, let me know. If anyone would like to see the full version, let me know also. An attempt at a proof that P != NP by Philip W---- 06/20/2008 The informal version: Formal proofs can be verified in polynomial time. Thus, the language of true statements with proofs of length bounded by a fixed polynomial is in NP. Therefore, we can construct an algorithm "B" such that B takes any formal statement as input, and attempts to find a proof of reasonable length for that statement. B will find any proof that is bounded by a specific polynomial, and is guaranteed to exist of P = NP. Furthermore, we can construct an algorithm of the following form: bool W(string x) { if (B("W(x) returns false") != ##FAIL /*##FAIL means no proof of reas. length*/) { return true; } else { return false; } } /*What it does: If B finds a proof of reasonable length that "W(x) returns false", return true. If B does not find such a proof, return false. */ If we look at the above function, we can easily prove Lemma A, which is as follows. Lemma A. Any function W of the above form, with any VALID proof generator (i.e., a proof generator that will generate either a correct proof or no proof at all) of ANY COMPLEXITY in place of B, must return false. We prove Lemma A formally by diagonalization; I omit this proof in this informal version. Informally, we can prove it by inspection; if, for some x, W(x) returns true, that means that B has found a proof that W(x) returns false--a contradiction. Therefore, W(x) must not return true. W(x) is clearly decidable (it halts on all inputs), and thus it returns false. Lemma A can be formalized--i.e., turned into a formal proof such that it might be generated by B. The existence of a polynomial-time proof generator B implies that B can generate a proof of Lemma A in polynomial time, provided that it is of reasonable length. Since Lemma A's proof is of a constant length, we can specify the polynomial bounds of B such that it will certainly find the proof of Lemma A. Furthermore, a proof that "W(x) returns false" immediately follows from Lemma A. Therefore, W(x) must return true in all situations. However, by Lemma A itself, W(x) is of such a form that it must return false. Thus we have a contradiction, and the algorithm B cannot exist. P = NP guarantees the existence of the algorithm B. Therefore, P != NP. --- Is this proof, as I have written it, understandable and clear? More to the point, is it accurate? I'm fairly worried that I missed something. Please let me know if anyone has any comments! Thanks very much, Phil
From: Patricia Shanahan on 22 Jun 2008 10:23 cplxphil(a)gmail.com wrote: .... > bool W(string x) > { > if (B("W(x) returns false") != ##FAIL /*##FAIL means no proof of > reas. length*/) > { > return true; > } > else > { > return false; > } > } > > /*What it does: If B finds a proof of reasonable length that "W(x) > returns false", return true. If B does not find such a proof, return > false. */ .... What does the formal version of this algorithm look like? On the face of it, it requires its own Goedel number, or other symbolic representation of itself, as embedded data in the quoted string. [This is just the first issue that I noticed - I have not studied the whole thing.] Patricia
From: PhilipJWhite on 22 Jun 2008 11:49 Yes, you are absolutely right. I realized about a day after posting this that that was the problem. The function I wrote makes perfect sense as pseudocode for a C++ function, but doesn't work as a Turing machine. I experimented with the idea of trying to make it work, but I actually don't think it's possible to have a function that calls itself as a Turing machine. Isn't that odd, though? I'm pretty sure C++ can't do things that Turing machine can't do. If you took my function and called it a C++ function, how would you translate what it does to a Turing machine or boolean circuit? -Phil On Jun 22, 10:23 am, Patricia Shanahan <p...(a)acm.org> wrote: > cplxp...(a)gmail.com wrote: > > ... > > > bool W(string x) > > { > > if (B("W(x) returns false") != ##FAIL /*##FAIL means no proof of > > reas. length*/) > > { > > return true; > > } > > else > > { > > return false; > > } > > } > > > /*What it does: If B finds a proof of reasonable length that "W(x) > > returns false", return true. If B does not find such a proof, return > > false. */ > > ... > > What does the formal version of this algorithm look like? On the face of > it, it requires its own Goedel number, or other symbolic representation > of itself, as embedded data in the quoted string. > > [This is just the first issue that I noticed - I have not studied the > whole thing.] > > Patricia
From: cplxphil on 22 Jun 2008 11:53 (Sorry, I think I clicked the wrong button when trying to reply earlier and sent the message to the wrong place.) Yes, you are definitely right...I realized that about a day after I posted. My proof requires a recursive definition of the function. But here's a question...this function makes perfect sense in C++, doesn't it? Turing machines can do anything C++ does, so what would this function look like if it were somehow translated to a Turing machine? Might it not be possible to somehow use pointers to make this function work somehow? -Phil On Jun 22, 10:23 am, Patricia Shanahan <p...(a)acm.org> wrote: > cplxp...(a)gmail.com wrote: > > ... > > > bool W(string x) > > { > > if (B("W(x) returns false") != ##FAIL /*##FAIL means no proof of > > reas. length*/) > > { > > return true; > > } > > else > > { > > return false; > > } > > } > > > /*What it does: If B finds a proof of reasonable length that "W(x) > > returns false", return true. If B does not find such a proof, return > > false. */ > > ... > > What does the formal version of this algorithm look like? On the face of > it, it requires its own Goedel number, or other symbolic representation > of itself, as embedded data in the quoted string. > > [This is just the first issue that I noticed - I have not studied the > whole thing.] > > Patricia
From: cplxphil on 22 Jun 2008 12:32
On Jun 22, 11:53 am, cplxp...(a)gmail.com wrote: > (Sorry, I think I clicked the wrong button when trying to reply > earlier and sent the message to the wrong place.) > > Yes, you are definitely right...I realized that about a day after I > posted. My proof requires a recursive definition of the function. > > But here's a question...this function makes perfect sense in C++, > doesn't it? Turing machines can do anything C++ does, so what would > this function look like if it were somehow translated to a Turing > machine? Might it not be possible to somehow use pointers to make > this function work somehow? > > -Phil > > On Jun 22, 10:23 am, Patricia Shanahan <p...(a)acm.org> wrote: > > > cplxp...(a)gmail.com wrote: > > > ... > > > > bool W(string x) > > > { > > > if (B("W(x) returns false") != ##FAIL /*##FAIL means no proof of > > > reas. length*/) > > > { > > > return true; > > > } > > > else > > > { > > > return false; > > > } > > > } > > > > /*What it does: If B finds a proof of reasonable length that "W(x) > > > returns false", return true. If B does not find such a proof, return > > > false. */ > > > ... > > > What does the formal version of this algorithm look like? On the face of > > it, it requires its own Goedel number, or other symbolic representation > > of itself, as embedded data in the quoted string. > > > [This is just the first issue that I noticed - I have not studied the > > whole thing.] > > > Patricia Ok, I have thought a little bit more about this. I think a simpler way to express my (flawed) proof is this: --- Let B be a polytime proof finder for statements that have proofs of reasonable length. If P = NP, B is guaranteed to exist. Consider this statement (rather than a function): W = B("W is false") returns a valid proof If W had a finite Godel number (which it does not), then we could diagonalize to prove that W must return false. We could then use the existence of that proof to find a contradiction, as B would then return a valid proof that W is false, leading to a contradiction. Unfortunately, I think it's probably impossible to ever fix this proof. The reason is this: If a proof of this nature could prove that no polytime algorithm like B exists, similar logic could be used to prove that no exponential time algorithm like B exists...and that is false, because proof-finding is in NP (or rather FNP), and exponentially-bounded algorithms have been found for NP-complete problems. Thus we would be able to prove something that is unprovable. Anyway, thanks for looking at the proof...at least now I know why it doesn't work. |