Science and Technology news... :: View topic - P does not equal NP

server · Guest

message unavailable

Guest

In article <d23df823-8cb8-434b-ba86-c9784b538791@b1g2000hsg.googlegroups.com>,
<cplxphil@gmail.com> wrote:
[quote]Michael Sipser wrote in an unpublished 1981 paper about the following
analogy:
"Polynomial growth is to exponential growth as countability is to
uncountability."
[...]
Perhaps this analogy could be used to solve the P = NP question...although
obviously no one has done so successfully yet.
[/quote]
The analogy *can* be used to prove that P != EXP. The argument that P != EXP
is similar in flavor to Cantor>s diagonal argument that a set and its power
set do not have the same cardinality, and for that reason is often referred
to as a "diagonalization argument."

I don>t know the Sipser paper you quote from, but the one sentence you cite
does not mention nondeterminism. My guess is that Sipser doesn>t think the
analogy has much value as far as P vs. NP goes, due to Baker-Gill-Solovay.

And of course, none of this has anything to do with the continuum hypothesis.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences

Guest

On Jun 28, 12:13 pm, tc...@lsa.umich.edu wrote:
[quote]In article <d23df823-8cb8-434b-ba86-c9784b538...@b1g2000hsg.googlegroups.com>,

cplxp...@gmail.com> wrote:
Michael Sipser wrote in an unpublished 1981 paper about the following
analogy:
"Polynomial growth is to exponential growth as countability is to
uncountability."
[...]
Perhaps this analogy could be used to solve the P = NP question...although
obviously no one has done so successfully yet.

The analogy *can* be used to prove that P != EXP. The argument that P != EXP
is similar in flavor to Cantor>s diagonal argument that a set and its power
set do not have the same cardinality, and for that reason is often referred
to as a "diagonalization argument."

I don>t know the Sipser paper you quote from, but the one sentence you cite
does not mention nondeterminism. My guess is that Sipser doesn>t think the
analogy has much value as far as P vs. NP goes, due to Baker-Gill-Solovay.

And of course, none of this has anything to do with the continuum hypothesis.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
[/quote]
You>re probably right...I don>t really know.

I>m just curious...what do those of you who are "non-amateurs" when it
comes to complexity theory think the right approach to solving P = NP
will ultimately be? I noticed Patricia Shanahan said that the
difficulty of proving it is related to eliminating the possibility of
some crazy NP-complete problem that is solvable. Does that
observation lead to a possible approach to solving it?

I know diagonalization doesn>t work (even though I doubted that for a
minute until someone cleared up what was wrong with my proof in
another thread), and I>ve read that someone named Razborov proved that
there is no "natural proof" that can work for proving a lower bound on
the complexity. What does that leave? I read somewhere that someone
said that it>s likely that whatever proof works will "involve
carefully analyzing how machines work" (or words to that effect), but
I don>t understand what that entails.

Any thoughts? I>ve been a sort of "P = NP hobbyist" for about a year
now, and I have no new ideas.

Does anyone think P = NP is true?

-Phil

Patricia Shanahan · Guest

cplxphil@gmail.com wrote:
....
[quote]I>m just curious...what do those of you who are "non-amateurs" when it
comes to complexity theory think the right approach to solving P = NP
will ultimately be? I noticed Patricia Shanahan said that the
difficulty of proving it is related to eliminating the possibility of
some crazy NP-complete problem that is solvable. Does that
observation lead to a possible approach to solving it?
[/quote]
I>m really an amateur as well. I have taken graduate courses in
complexity theory, but it is neither my professional field nor my
current research topic.

If P=NP and it is ever proved, I expect it to be through some wild piece
of mathematics leading to an insight into the domain of one of the NPC
problems.

I have no idea how to prove P is not equal to NP, though I strongly
suspect it is true.

The flaw I>ve seen in claimed attempts to prove it is that they make
some unjustified assumption about the form of algorithms for solving the
NPC problems. A valid proof would have to either not involve any
assumption, other than "can be represented as a Turing machine", or
would contain a proof of any assumption that is made.

Patricia

Guest

On Jun 28, 12:09 am, matt.timmerm...@gmail.com wrote:
[quote]Hi Phil,

Your proof that algorithm B does not exist works just as well if B is
allowed to take exponential time, or even unbounded time (as long as
it stops), so it has no bearing on whether or not P = NP.

In fact, what you are proving is Goedel>s theorem: If you can express
"W(W) returns false" in your formal system, then it is either
incomplete in that it has no proof of that statement, or inconsistent
in that it can prove a statement that is not true.

Cheers,

Matt
[/quote]
Ok, I agree with point one; you are certainly correct that my proof
couldn>t possibly have any bearing on whether or not P = NP, because
of what you mentioned about exponential time. However, I have an
unresolved reservation pertaining to your claim that I am re-proving
Godel>s incompleteness theorem.

Here is my problem. Let>s assume that you are correct that "W(W)
returns false" is undecidable. Here is the function again:

bool W (algorithm X)
{
if (B("X(X) returns false") != "##FAIL")
{
return true;
}
else
{
return false;
}

}

If "X(X) returns false" is undecidable when X = W, then the if
statement will evaluate to ##FAIL, because no proof will be found.
Thus, the function will return false...and then W(W) is no longer
undecidable. Therefore, it is impossible for W(W) to be undecidable.

I do agree with your initial point, but there is something else going
on here. I think I have actually proven something interesting, even
if it>s not P = NP. I have a theory that I>m not sure is correct, but
I think that what I may have proven is that the diagonalization proof
I was talking about must be of length greater than one billion
characters, for some reason that I cannot understand.

Does what I>m saying make sense? I don>t think I made a mistake, but
if I did please let me know. I>m almost positive this is not Godel>s
incompleteness theorem.

-Phil

Guest

On Jun 28, 12:09 am, matt.timmerm...@gmail.com wrote:
[quote]Hi Phil,

Your proof that algorithm B does not exist works just as well if B is
allowed to take exponential time, or even unbounded time (as long as
it stops), so it has no bearing on whether or not P = NP.

In fact, what you are proving is Goedel>s theorem: If you can express
"W(W) returns false" in your formal system, then it is either
incomplete in that it has no proof of that statement, or inconsistent
in that it can prove a statement that is not true.

Cheers,

Matt
[/quote]
On Jun 28, 12:09 am, matt.timmerm...@gmail.com wrote:

[quote]Hi Phil,

Your proof that algorithm B does not exist works just as well if B is
allowed to take exponential time, or even unbounded time (as long as
it stops), so it has no bearing on whether or not P = NP.

In fact, what you are proving is Goedel>s theorem: If you can express
"W(W) returns false" in your formal system, then it is either
incomplete in that it has no proof of that statement, or inconsistent
in that it can prove a statement that is not true.

Cheers,

Matt
[/quote]

Matt,

Ok, I agree with point one; you are certainly correct that my proof
couldn>t possibly have any bearing on whether or not P = NP, because
of what you mentioned about exponential time. I initially agreed with
your second point also. However, I have an
unresolved reservation pertaining to your claim that I am re-proving
Godel>s incompleteness theorem.

Here is my problem. Let>s assume that you are correct that "W(W)
returns false" is undecidable. Here is the function again:

bool W (algorithm X)
{
if (B("X(X) returns false") != "##FAIL")
{
return true;
}
else
{
return false;
}

}

If "X(X) returns false" is undecidable when X = W, then the if
statement will evaluate to ##FAIL, because no proof will be found.
Thus, the function will return false...and then W(W) is no longer
undecidable. Therefore, it is impossible for W(W) to be undecidable.

I do agree with your initial point, but there is something else going
on here. I think I have actually proven something interesting, even
if it>s not P = NP. I have a theory that I>m not sure is correct, but
I think that what I may have proven is that the diagonalization proof
I was talking about must be of length greater than one billion
characters, for some reason that I cannot understand.

Does what I>m saying make sense? I don>t think I made a mistake, but
if I did please let me know. I>m almost positive this is not Godel>s
incompleteness theorem.

-Phil

Guest

Matt,

Ok, I agree with point one; you are certainly correct that my proof
couldn>t possibly have any bearing on whether or not P = NP, because
of what you mentioned about exponential time. I initially agreed with
your second point also. However, I have an
unresolved reservation pertaining to your claim that I am re-proving
Godel>s incompleteness theorem.

Here is my problem. Let>s assume that you are correct that "W(W)
returns false" is undecidable. Here is the function again:

bool W (algorithm X)
{
if (B("X(X) returns false") != "##FAIL")
{
return true;
}
else
{
return false;
}

}

If "X(X) returns false" is undecidable when X = W, then the if
statement will evaluate to ##FAIL, because no proof will be found.
Thus, the function will return false...and then W(W) is no longer
undecidable. Therefore, it is impossible for W(W) to be undecidable.

I do agree with your initial point, but there is something else going
on here. I think I have actually proven something interesting, even
if it>s not P != NP. I have a theory that I>m not sure is correct,
but
I think that what I may have proven is that the diagonalization proof
I was talking about must be of length greater than one billion
characters, for some reason that I cannot understand.

Does what I>m saying make sense? I don>t think I made a mistake, but
if I did please let me know. I>m almost positive this is not Godel>s
incompleteness theorem.

-Phil

Guest

Hi Phil,

On Jun 29, 1:45 pm, cplxp...@gmail.com wrote:
[quote]Here is my problem. Let>s assume that you are correct that "W(W)
returns false" is undecidable.
[/quote]
Oh no, not undecidable -- that>s the stopping problem proof. Let me
rearrange your work a bit:

[quote]I think that what I may have proven is that the diagonalization proof
I was talking about must be of length greater than one billion
characters, for some reason that I cannot understand.
[/quote]
That is a loophole in your argument that we can get rid of by using
non-halting to replace your notion of returning false.

Let>s start again without the billion character limit...

Assume that we have some formal system in which propositions and
proofs about algorithms may be written. Given any such formal system,
we can write a proof finding algorithm B that accepts a propostion and
tries all proofs, from the shortest to the longest, until it finds a
proof of the proposition. When it finds a proof it returns true. If
it finds no such proof, it doesn>t halt.
Then, we write:

bool W(algorithm X)
{
if (B("X(X) doesn>t halt"))
{
return true;
}
else
{
spin_forever();
}
}

And we run W(W).

Now, I hope you agree that this is pretty much the same scenario you
proposed, and your argument is that this construction is impossible,
since it implies that W(W) halts if and only if it doesn>t halt -- a
contradiction. However, I have told you above exactly how to write
B() and W(), and so B() obviously _does_ exist, and this construction
obviously _is_ possible, so there must be some flaw in your reasoning.

The problem with your proof is that you never consider the formal
system in which the proofs that B() finds are written. You assume
that it is both complete, in that it has a proof for whatever you can
prove in text, and consistent with reality to the extent that whatever
it can prove about itself is actually true. And this is exactly what
Goedel proved that you cannot assume.

In fact, B() does exist, W() exists, and you can run W(W). Does it
return true or spin forever? Both are possible:

- If it returns true, then there is a proof of "W(W) doesn>t halt" in
your formal system, but W(W) actually does halt. Your formal system
is, in this case, inconsistent.

- If it spins forever, then there is no such proof, even though the
proposition is true. Your formal system is, in this case, incomplete.

[quote]I>m almost positive this is not Godel>s incompleteness theorem.
[/quote]
I hope I>ve shown you that this is indeed Goedel>s theorem, but
applied explicitly to formal systems of reasoning about algorithms.
Of course, you can also see that the proof is very similar to the
stopping problem proof, and in this scope Goedel>s theorem and
stopping undecidability are essentially equivalent. The only
difference is that here we have explicitly included into our
consideration formal systems that give wrong (inconsistent) answers.
Goedel proved that any formal system of reasoning about natural
numbers (which includes reasoning about algorithms) is incomplete or
inconsistent. Turing proved that every consistent system of reasoning
about algorithms is incomplete.

Cheers,

Matt

Bhupinder Singh Anand · Guest

On Jun 29, 5:53 am, Patricia Shanahan <p...@acm.org> wrote in
comp.theory:

PS>> A valid proof would have to either not involve any assumption,
other than "can be represented as a Turing machine", or would contain
a proof of any assumption that is made. <<PS

Patricia
=======
Yes, that>s what I have attempted in a paper to be published in the
proceedings of the 2008 International Conference on Foundations of
Computer Science, July 14-17, 2008, Las Vegas, USA:

http://alixcomsi.com/18_A_trivial_solution_to_PvNP.pdf

Regards,

Bhup

Guest

On Jun 29, 9:23 pm, matt.timmerm...@gmail.com wrote:
[quote]Hi Phil,

On Jun 29, 1:45 pm, cplxp...@gmail.com wrote:

Here is my problem. Let>s assume that you are correct that "W(W)
returns false" is undecidable.

Oh no, not undecidable -- that>s the stopping problem proof. Let me
rearrange your work a bit:

I think that what I may have proven is that the diagonalization proof
I was talking about must be of length greater than one billion
characters, for some reason that I cannot understand.

That is a loophole in your argument that we can get rid of by using
non-halting to replace your notion of returning false.

Let>s start again without the billion character limit...

Assume that we have some formal system in which propositions and
proofs about algorithms may be written. Given any such formal system,
we can write a proof finding algorithm B that accepts a propostion and
tries all proofs, from the shortest to the longest, until it finds a
proof of the proposition. When it finds a proof it returns true. If
it finds no such proof, it doesn>t halt.
Then, we write:

bool W(algorithm X)
{
if (B("X(X) doesn>t halt"))
{
return true;
}
else
{
spin_forever();
}

}

And we run W(W).

Now, I hope you agree that this is pretty much the same scenario you
proposed, and your argument is that this construction is impossible,
since it implies that W(W) halts if and only if it doesn>t halt -- a
contradiction. However, I have told you above exactly how to write
B() and W(), and so B() obviously _does_ exist, and this construction
obviously _is_ possible, so there must be some flaw in your reasoning.

The problem with your proof is that you never consider the formal
system in which the proofs that B() finds are written. You assume
that it is both complete, in that it has a proof for whatever you can
prove in text, and consistent with reality to the extent that whatever
it can prove about itself is actually true. And this is exactly what
Goedel proved that you cannot assume.

In fact, B() does exist, W() exists, and you can run W(W). Does it
return true or spin forever? Both are possible:

- If it returns true, then there is a proof of "W(W) doesn>t halt" in
your formal system, but W(W) actually does halt. Your formal system
is, in this case, inconsistent.

- If it spins forever, then there is no such proof, even though the
proposition is true. Your formal system is, in this case, incomplete.

I>m almost positive this is not Godel>s incompleteness theorem.

I hope I>ve shown you that this is indeed Goedel>s theorem, but
applied explicitly to formal systems of reasoning about algorithms.
Of course, you can also see that the proof is very similar to the
stopping problem proof, and in this scope Goedel>s theorem and
stopping undecidability are essentially equivalent. The only
difference is that here we have explicitly included into our
consideration formal systems that give wrong (inconsistent) answers.
Goedel proved that any formal system of reasoning about natural
numbers (which includes reasoning about algorithms) is incomplete or
inconsistent. Turing proved that every consistent system of reasoning
about algorithms is incomplete.

Cheers,

Matt
[/quote]

I hate to be obstinate, but you have totally changed the nature of my
proof. My proof has nothing to do with the halting problem; you
introduce the notion of halting into the proof with the statement
"X(X) doesn>t halt." Of course if you re-write my proof so that it>s
Turing>s halting problem proof, you will get a different result. By
"re-arranging" my proof, you>ve totally changed the character of it.
Additionally, Godel>s proof does pertain to undecidability. Godel
proved that no formal system is complete and consistent by
demonstrating that undecidable propositions exist in all consistent
formal systems.

The "loophole" that you suggest the billion-character limit provides
is actually crucial to my proof.

-Phil

Guest

On Jun 29, 9:23 pm, matt.timmerm...@gmail.com wrote:
[quote]Hi Phil,

On Jun 29, 1:45 pm, cplxp...@gmail.com wrote:

Here is my problem. Let>s assume that you are correct that "W(W)
returns false" is undecidable.

Oh no, not undecidable -- that>s the stopping problem proof. Let me
rearrange your work a bit:

I think that what I may have proven is that the diagonalization proof
I was talking about must be of length greater than one billion
characters, for some reason that I cannot understand.

That is a loophole in your argument that we can get rid of by using
non-halting to replace your notion of returning false.

Let>s start again without the billion character limit...

Assume that we have some formal system in which propositions and
proofs about algorithms may be written. Given any such formal system,
we can write a proof finding algorithm B that accepts a propostion and
tries all proofs, from the shortest to the longest, until it finds a
proof of the proposition. When it finds a proof it returns true. If
it finds no such proof, it doesn>t halt.
Then, we write:

bool W(algorithm X)
{
if (B("X(X) doesn>t halt"))
{
return true;
}
else
{
spin_forever();
}

}

And we run W(W).

Now, I hope you agree that this is pretty much the same scenario you
proposed, and your argument is that this construction is impossible,
since it implies that W(W) halts if and only if it doesn>t halt -- a
contradiction. However, I have told you above exactly how to write
B() and W(), and so B() obviously _does_ exist, and this construction
obviously _is_ possible, so there must be some flaw in your reasoning.

The problem with your proof is that you never consider the formal
system in which the proofs that B() finds are written. You assume
that it is both complete, in that it has a proof for whatever you can
prove in text, and consistent with reality to the extent that whatever
it can prove about itself is actually true. And this is exactly what
Goedel proved that you cannot assume.

In fact, B() does exist, W() exists, and you can run W(W). Does it
return true or spin forever? Both are possible:

- If it returns true, then there is a proof of "W(W) doesn>t halt" in
your formal system, but W(W) actually does halt. Your formal system
is, in this case, inconsistent.

- If it spins forever, then there is no such proof, even though the
proposition is true. Your formal system is, in this case, incomplete.

I>m almost positive this is not Godel>s incompleteness theorem.

I hope I>ve shown you that this is indeed Goedel>s theorem, but
applied explicitly to formal systems of reasoning about algorithms.
Of course, you can also see that the proof is very similar to the
stopping problem proof, and in this scope Goedel>s theorem and
stopping undecidability are essentially equivalent. The only
difference is that here we have explicitly included into our
consideration formal systems that give wrong (inconsistent) answers.
Goedel proved that any formal system of reasoning about natural
numbers (which includes reasoning about algorithms) is incomplete or
inconsistent. Turing proved that every consistent system of reasoning
about algorithms is incomplete.

Cheers,

Matt
[/quote]

I hate to be obstinate, but you have totally changed the nature of my
proof. My proof has nothing to do with the halting problem; you
introduce the notion of halting into the proof with the statement
"X(X) doesn>t halt." Of course if you re-write my proof so that it>s
Turing>s halting problem proof, you will get a different result. By
"re-arranging" my proof, you>ve totally changed the character of it.
Additionally, Godel>s proof does pertain to undecidability. Godel
proved that no formal system is complete and consistent by
demonstrating that undecidable propositions exist in all consistent
formal systems.

The "loophole" that you suggest the billion-character limit provides
is actually crucial to my proof.

-Phil

Guest

On Jun 30, 9:04 am, cplxp...@gmail.com wrote:
[quote]The "loophole" that you suggest the billion-character limit provides
is actually crucial to my proof.
[/quote]
Crucial to your proof of what, exactly?

[quote]On Jun 29, 9:23 pm, matt.timmerm...@gmail.com wrote:
I hate to be obstinate, but you have totally changed the nature of my
proof.
[/quote]
Well, yes, I "fixed" it until it proved something. You could
certainly fix it some other way, to prove something else.

You could certainly prove that any proof of a certain proposition in a
complete and consistent formal system must be > 1 billion characters
long, but that is much weaker than proving that no such formal system
exists, which Goedel has already done. I doubt that this is your
goal.

--
Matt

Guest

On Jun 30, 11:32 am, matt.timmerm...@gmail.com wrote:
[quote]On Jun 30, 9:04 am, cplxp...@gmail.com wrote:

The "loophole" that you suggest the billion-character limit provides
is actually crucial to my proof.

Crucial to your proof of what, exactly?

On Jun 29, 9:23 pm, matt.timmerm...@gmail.com wrote:
I hate to be obstinate, but you have totally changed the nature of my
proof.

Well, yes, I "fixed" it until it proved something. You could
certainly fix it some other way, to prove something else.

You could certainly prove that any proof of a certain proposition in a
complete and consistent formal system must be > 1 billion characters
long, but that is much weaker than proving that no such formal system
exists, which Goedel has already done. I doubt that this is your
goal.

--
Matt
[/quote]

Okay, I am sorry. I did not make clear what I was going for; if I had
done that perhaps you would have understood.

What I think I have proven is indeed much weaker than Godel>s
incompleteness theorem; however, I still find it interesting. I
believe that what I>ve proven is that there are proofs that can be
argued informally and very briefly but that take a huge amount of bits
to actually prove formally. You could replace "one billion" with "one
googleplex"; either way, you are dealing with a proof that can be
argued informally to be true quite rapidly, but that is formally
unprovable unless a huge number of bits are used.

Anyway, no one needs to waste any more time with the proof. I
appreciate all the feedback that you>ve given.

Thanks,
Phil

Jamie Andrews; real addre · Guest

[quote]On Jun 29, 5:53 am, Patricia Shanahan <p...@acm.org> wrote:
PS>> A valid proof would have to either not involve any assumption,
other than "can be represented as a Turing machine", or would contain
a proof of any assumption that is made. <<PS
[/quote]
Bhupinder Singh Anand <anandb@vsnl.com> wrote:
[quote]Yes, that>s what I have attempted in a paper to be published in the
proceedings of the 2008 International Conference on Foundations of
Computer Science, July 14-17, 2008, Las Vegas, USA:
http://alixcomsi.com/18_A_trivial_solution_to_PvNP.pdf
[/quote]
I can find no record of any paper by this name or any paper
by a Bhupinder Singh Anand in the conference program of that
conference.

--Jamie. (efil4dreN)
andrews .uwo } Merge these two lines to obtain my e-mail address.
@csd .ca } (Unsolicited "bulk" e-mail costs everyone.)

Hans Hüttel · Guest

In article
<2223bc46-5bd6-49dc-8521-2018c8ad19ca@m3g2000hsc.googlegroups.com>,
Eric Bodden <eric.bodden@googlemail.com> wrote:

[quote]I am currently writing a paper about an analysis that should be
feasible for any computational system for which one can decide
reachability of configurations, e.g. finite state machines, petri nets
etc. This made me wonder: Is there any concise classification of
"languages for which reachability is decidable"?

I know that reachability is undecidable for Turing-complete systems
but I am not sure if the inverse direction also holds. Are there non-
Turing-complete languages for which reachability is undecidable or
does "non-Turing-complete" somehow imply that one can decide
reachability?

Hope you see what I mean ;-)
[/quote]
First I should warn you that this is not my research area. But I do know
that Petri nets are not Turing-powerful and their reachability problem
is decidable, but hard, so a natural candidate would be an extension of
Petri nets.

Timed-arc Petri nets are not Turing-powerful but reachability is
undecidable. See e.g.

http://www.informatik.uni-hamburg.de/TGI/pnbib/v/valero_ruiz_v1.html

--
Hans Hüttel
Department of Computer Science
Aalborg University
Denmark


www.GetXFactor.com Leading Technology, Science, Agriculture News and information	Part of the Identityscape.com network... getxfactor.com jmoodmusic.com smartbusinesschoices.com mintdepot.com lowfaresalways.com evangelicalview.com shoppingpodder.com soproudlywehail.com webnews.ws currenthumor.com

Science and Technology news... Forum Index -> Cryptography Forum	Goto page 1, 2, 3, 4 Next
Page 1 of 4