Could P = NP be true?
in [Theory]
|
Prev: Symposium “Image Processing and Analysis” within the ICCES'10 USA - Announce & Call for Contributions
Next: Workshop “Medical Imaging Systems” within EUROMEDIA 2010 – Announce & Call for Papers
From: cplxphil on 14 Dec 2009 11:25 Most people seem to think that P = NP is almost certainly false. I was wondering about a possible scenario where P = NP might be true. Generally speaking, it seems that in order to prove that a decision problem belongs to a certain complexity class, one has to find an algorithm to solve it. For example, I would imagine it would be difficult to prove that the shortest path problem can be solved in polynomial time without demonstrating an algorithm (or the equivalent, such as a query) to solve it. What if P = NP is true, but every algorithm that solves an NP- complete in polynomial time is a) really bad (e.g., O(n^1000000000) or something), and b) impossible to prove correct--that is, for every machine M that decides SAT in polynomial time, there does not exist a proof that M solves SAT in polynomial time? Then, the reason that P = NP is so hard to resolve would be not that there are diagonalization and natural proof barriers to proving it false, but rather that there is a barrier to proving it true. Does this seem plausible? -Phil (I am aware of the multi-tasking algorithm that provably accepts SAT iff P = NP, but I don't think it's definitely possible to prove that any algorithm actually *decides* SAT without proving that ZFC is consistent, which cannot be done.)
From: tchow on 14 Dec 2009 12:51 In article <e3f7a638-85cd-4cca-bc16-30aacb3a67c3(a)j14g2000yqm.googlegroups.com>, cplxphil <cplxphil(a)gmail.com> wrote: >Then, the reason that P = NP is so hard to resolve would be not that >there are diagonalization and natural proof barriers to proving it >false, but rather that there is a barrier to proving it true. > >Does this seem plausible? Possible, yes. Plausible, not so much. By the way, there do exist cases where we know that a polynomial-time algorithm exists but have not exhibited an algorithm. The most notable examples come from graph minor theory. From Robertson and Seymour's graph minor theorem, plus the fact that testing for the presence of a given minor is solvable in polynomial time, we know that any hereditary graph property is checkable in polynomial time. But to exhibit the algorithm, we have to exhibit the finite list of forbidden minors, and there is no general method of computing that list. -- 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
From: cplxphil on 14 Dec 2009 15:20 On Dec 14, 12:51 pm, tc...(a)lsa.umich.edu wrote: > In article <e3f7a638-85cd-4cca-bc16-30aacb3a6...(a)j14g2000yqm.googlegroups..com>, > > cplxphil <cplxp...(a)gmail.com> wrote: > >Then, the reason that P = NP is so hard to resolve would be not that > >there are diagonalization and natural proof barriers to proving it > >false, but rather that there is a barrier to proving it true. > > >Does this seem plausible? > > Possible, yes. Plausible, not so much. Why not? > > By the way, there do exist cases where we know that a polynomial-time > algorithm exists but have not exhibited an algorithm. The most notable > examples come from graph minor theory. From Robertson and Seymour's > graph minor theorem, plus the fact that testing for the presence of a > given minor is solvable in polynomial time, we know that any hereditary > graph property is checkable in polynomial time. But to exhibit the > algorithm, we have to exhibit the finite list of forbidden minors, and > there is no general method of computing that list. That is interesting, I'll look into that. Thanks. -Phil
From: Casey Hawthorne on 14 Dec 2009 18:39 On Mon, 14 Dec 2009 08:25:05 -0800 (PST), cplxphil <cplxphil(a)gmail.com> wrote: > >Most people seem to think that P = NP is almost certainly false. I >was wondering about a possible scenario where P = NP might be true. > >Generally speaking, it seems that in order to prove that a decision >problem belongs to a certain complexity class, one has to find an >algorithm to solve it. For example, I would imagine it would be >difficult to prove that the shortest path problem can be solved in >polynomial time without demonstrating an algorithm (or the equivalent, >such as a query) to solve it. > >What if P = NP is true, but every algorithm that solves an NP- >complete in polynomial time is a) really bad (e.g., O(n^1000000000) >or something), and b) impossible to prove correct--that is, for every >machine M that decides SAT in polynomial time, there does not exist a >proof that M solves SAT in polynomial time? > >Then, the reason that P = NP is so hard to resolve would be not that >there are diagonalization and natural proof barriers to proving it >false, but rather that there is a barrier to proving it true. > >Does this seem plausible? > >-Phil > There is a major gap between computabiltiy theory and complexity theory. We have a good grasp of the separation between what is and what is not computable; however, for complexity theory, we are missing provable good lower bounds on the NP problem class. >(I am aware of the multi-tasking algorithm that provably accepts SAT >iff P = NP, but I don't think it's definitely possible to prove that >any algorithm actually *decides* SAT without proving that ZFC is >consistent, which cannot be done.) -- Regards, Casey
From: tchow on 14 Dec 2009 22:00
In article <8bec1657-039e-4c80-b153-a025e0182b33(a)v30g2000yqm.googlegroups.com>, cplxphil <cplxphil(a)gmail.com> wrote: >On Dec 14, 12:51�pm, tc...(a)lsa.umich.edu wrote: >> In article >> <e3f7a638-85cd-4cca-bc16-30aacb3a6...(a)j14g2000yqm.googlegroups.com>, >> >> cplxphil �<cplxp...(a)gmail.com> wrote: >> >Then, the reason that P = NP is so hard to resolve would be not that >> >there are diagonalization and natural proof barriers to proving it >> >false, but rather that there is a barrier to proving it true. >> >> >Does this seem plausible? >> >> Possible, yes. �Plausible, not so much. > >Why not? For me to label something "plausible," I need some positive evidence in that direction. I see very little positive evidence that P = NP. Furthermore, I see no positive evidence that P = NP is unprovable. I often see people confusing the *psychological difficulty* of resolving a mathematical question with the *logical strength* of the axiomatic system needed to resolve it. There is plenty of evidence that P = NP is a challenging problem for human minds, but I do not regard this as evidence that the logical strength of the axiomatic system needed to resolve P = NP is high. -- 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 |