Re: What's wrong with this proof that P = NP?
- From: cplxphil@xxxxxxxxx
- Date: Sun, 22 Jun 2008 09:32:23 -0700 (PDT)
On Jun 22, 11:53 am, cplxp...@xxxxxxxxx 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...@xxxxxxx> wrote:
cplxp...@xxxxxxxxx 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.
.
- References:
- What's wrong with this proof that P = NP?
- From: cplxphil
- Re: What's wrong with this proof that P = NP?
- From: cplxphil
- What's wrong with this proof that P = NP?
- Prev by Date: Re: What's wrong with this proof that P = NP?
- Next by Date: Re: P does not equal NP - a logical approach
- Previous by thread: Re: What's wrong with this proof that P = NP?
- Next by thread: Re: What's wrong with this proof that P = NP?
- Index(es):
Relevant Pages
|
