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: RussellE on 16 Dec 2009 16:31 On Dec 14, 7:00 pm, tc...(a)lsa.umich.edu wrote: > In article <8bec1657-039e-4c80-b153-a025e0182...(a)v30g2000yqm.googlegroups..com>, > > cplxphil <cplxp...(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. I think there is a lot of positive evidence that P = NP might be true. Many NP problems, like 2SAT, have known polynomial algorithms. Even most NP-Complete instances, like 3SAT, can be solved in polytime. Most solvable 3SAT instances can be solved in polytime by a random guessing algorithm. Only a small class of 3SAT instances are "hard". If all NP-Complete problems were "hard", we wouldn't have commercial SAT solvers. Last, but not least, no one has proven P =/= NP. So far, I see no reason why P = NP can't be true. Russell - 2 many 2 count
From: tchow on 16 Dec 2009 21:42 In article <0a2491d0-d80f-49fa-98f2-f4fcd152a04f(a)e4g2000prn.googlegroups.com>, RussellE <reasterly(a)gmail.com> wrote: >I think there is a lot of positive evidence that P = NP might be true. I'm afraid I don't find your arguments convincing. >Many NP problems, like 2SAT, have known polynomial algorithms. Many problems in EXPTIME, like 2SAT, have known polynomial algorithms. >Even most NP-Complete instances, like 3SAT, can be solved in polytime. >Most solvable 3SAT instances can be solved in polytime by a random >guessing algorithm. Only a small class of 3SAT instances are "hard". Average-case complexity doesn't say much about worst-case complexity, which is what the P = NP question is about. >If all NP-Complete problems were "hard", we wouldn't have commercial >SAT solvers. That's absurd. If a problem is hard but important, then people will do the best they can. Perhaps you just mean that if all NP-complete problems were hard on average then commercial SAT solvers would do poorly all the time. That might be true, but it's irrelevant to the question of worst-case complexity. >Last, but not least, no one has proven P =/= NP. True enough. But nobody has proven P = NP either, so I don't see this fact as positive evidence for either direction. >So far, I see no reason why P = NP can't be true. Neither can I. That wasn't the question. The question was not whether P = NP *could* be true, but whether there was any *positive evidence* for it. You haven't presented any. -- 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: RussellE on 17 Dec 2009 15:21 On Dec 16, 6:42 pm, tc...(a)lsa.umich.edu wrote: > In article <0a2491d0-d80f-49fa-98f2-f4fcd152a...(a)e4g2000prn.googlegroups.com>, > > RussellE <reaste...(a)gmail.com> wrote: > >I think there is a lot of positive evidence that P = NP might be true. > > I'm afraid I don't find your arguments convincing. > > >Many NP problems, like 2SAT, have known polynomial algorithms. > > Many problems in EXPTIME, like 2SAT, have known polynomial algorithms. > > >Even most NP-Complete instances, like 3SAT, can be solved in polytime. > >Most solvable 3SAT instances can be solved in polytime by a random > >guessing algorithm. Only a small class of 3SAT instances are "hard". > > Average-case complexity doesn't say much about worst-case complexity, > which is what the P = NP question is about. We can't even define "worst case complexity" for 3SAT. A 3SAT instance that is hard for one solver might be easily solved by a different solver. We do know that instances with a certain variable to clause ratio tend to be more difficult, but even this tells us nothing about how "hard" a specific instance might be. This inability to even define "worst case" is one reason I find the P=NP problem interesting. > >If all NP-Complete problems were "hard", we wouldn't have commercial > >SAT solvers. > > That's absurd. If a problem is hard but important, then people will do the > best they can. "The best they can" turns out to be pretty good. Modern SAT solvers can find satisfying assignments very quickly for most instances. > Perhaps you just mean that if all NP-complete problems were > hard on average then commercial SAT solvers would do poorly all the time. > That might be true, but it's irrelevant to the question of worst-case > complexity. I would say we have already proven P=NP for all practical purposes. Yes, there are "small" 3SAT instance (300 variables) that can't be solved by modern SAT solvers in a "reasonable" time. But, such instances are the exception, not the rule. SAT solvers can and have solved instances with 10,000 variables. Even the "hard" 300 variable instances can be solved if we are willing to wait long enough. Polynomial doesn't necessarily mean efficient. N^10 is polynomial, but I wouldn't want to wait for a solver to do 300^10 operations. > >Last, but not least, no one has proven P =/= NP. > > True enough. But nobody has proven P = NP either, so I don't see this fact > as positive evidence for either direction. I agree. The lack of a proof ether way doesn't tell us much. And I agree there are reasons to suspect P=/=NP. Like you, I have read a number of "proofs" of P=/=NP. I even have one myself. I think I can prove 3SAT can't be converted to 2SAT. Some 3SAT instances can't even be converted to a polynomial number of 2SAT instances. This still doesn't rule out the possibility of finding one satisfying assignment in polynomial time. As for positive evidence for P=NP, I would look at the published lower bounds. These bounds are already quite low (but still exponential) and new lower bounds are being published all the time. Russell - 2 many 2 count
From: cplxphil on 17 Dec 2009 16:36 On Dec 17, 3:21 pm, RussellE <reaste...(a)gmail.com> wrote: > On Dec 16, 6:42 pm, tc...(a)lsa.umich.edu wrote: > > > > > > > In article <0a2491d0-d80f-49fa-98f2-f4fcd152a...(a)e4g2000prn.googlegroups.com>, > > > RussellE <reaste...(a)gmail.com> wrote: > > >I think there is a lot of positive evidence that P = NP might be true. > > > I'm afraid I don't find your arguments convincing. > > > >Many NP problems, like 2SAT, have known polynomial algorithms. > > > Many problems in EXPTIME, like 2SAT, have known polynomial algorithms. > > > >Even most NP-Complete instances, like 3SAT, can be solved in polytime. > > >Most solvable 3SAT instances can be solved in polytime by a random > > >guessing algorithm. Only a small class of 3SAT instances are "hard". > > > Average-case complexity doesn't say much about worst-case complexity, > > which is what the P = NP question is about. > > We can't even define "worst case complexity" for 3SAT. > A 3SAT instance that is hard for one solver might be easily solved > by a different solver. We do know that instances with a certain > variable to clause ratio tend to be more difficult, but even this > tells us nothing about how "hard" a specific instance might be. > > This inability to even define "worst case" is one reason I > find the P=NP problem interesting. > Worst-case complexity is definitely defined. The fact that we don't know what it is is the reason why P = NP remains unresolved. > > >If all NP-Complete problems were "hard", we wouldn't have commercial > > >SAT solvers. > > > That's absurd. If a problem is hard but important, then people will do the > > best they can. > > "The best they can" turns out to be pretty good. Modern SAT solvers > can find satisfying assignments very quickly for most instances. > That is irrelevant. The problem is that most of the SAT instances people really care about--e.g., the ones generated for cryptographic purposes--cannot be solved. "Most instances" is essentially meaningless. The P = NP problem is to find a single algorithm that decides *all* SAT instances in polynomial time. > > Perhaps you just mean that if all NP-complete problems were > > hard on average then commercial SAT solvers would do poorly all the time. > > That might be true, but it's irrelevant to the question of worst-case > > complexity. > > I would say we have already proven P=NP for all practical purposes. > Yes, there are "small" 3SAT instance (300 variables) that can't be > solved by modern SAT solvers in a "reasonable" time. > But, such instances are the exception, not the rule. SAT solvers can > and have solved instances with 10,000 variables. > > Even the "hard" 300 variable instances can be solved if we are > willing > to wait long enough. Polynomial doesn't necessarily mean efficient. ....if we are willing to wait long enough? What? No, polynomial-bounded doesn't necessarily mean efficient; but it does have a definition. > N^10 is polynomial, but I wouldn't want to wait for a solver to do > 300^10 > operations. > > > >Last, but not least, no one has proven P =/= NP. > > > True enough. But nobody has proven P = NP either, so I don't see this fact > > as positive evidence for either direction. > > I agree. The lack of a proof ether way doesn't tell us much. > And I agree there are reasons to suspect P=/=NP. Like you, > I have read a number of "proofs" of P=/=NP. I even have one myself. > I think I can prove 3SAT can't be converted to 2SAT. Some 3SAT > instances can't even be converted to a polynomial number of 2SAT > instances. > > This still doesn't rule out the possibility of finding one satisfying > assignment in polynomial time. As you said above, polynomial doesn't mean efficient. > > As for positive evidence for P=NP, I would look at the published lower > bounds. > These bounds are already quite low (but still exponential) and new > lower bounds are being published all the time. You mean upper bounds, right? > > Russell > - 2 many 2 count Have you read and understood Stephen Cook's paper on the P vs. NP problem? If not, it's a good first step. That is how I first got introduced to the problem. Here is a link: http://www.claymath.org/millennium/P_vs_NP/ It's not my intent to insult you, but you don't sound like you understand even the basics of the P vs. NP problem. You would probably benefit greatly from doing some more reading and keeping an open mind. It is a very fascinating problem. -Phil
From: Joshua Cranmer on 17 Dec 2009 17:45
On 12/17/2009 04:36 PM, cplxphil wrote: >> "The best they can" turns out to be pretty good. Modern SAT solvers >> can find satisfying assignments very quickly for most instances. >> > > That is irrelevant. The problem is that most of the SAT instances > people really care about--e.g., the ones generated for cryptographic > purposes--cannot be solved. "Most instances" is essentially > meaningless. The P = NP problem is to find a single algorithm that > decides *all* SAT instances in polynomial time. Cryptography purposefully tries to find hard instances of problems. I can find a factor of 2/3 of all numbers in two steps: try dividing by 2 and then try dividing by 3. The problem space of "hard" numbers to factors is relatively tiny compared to the general scope of integers. Many NP-complete problems filter down to common practical applications: traveling salesman (circuit board design), graph coloring (compiling code), etc. For these applications, the pathological cases are much rarer. So, "most" is generally good enough for practical purposes. I'm specifically excluding the choice of cryptography when I'm referring to "practical" in this case. > It's not my intent to insult you, but you don't sound like you > understand even the basics of the P vs. NP problem. You would > probably benefit greatly from doing some more reading and keeping an > open mind. It is a very fascinating problem. I suspect he understands it, perhaps in greater detail than you do. He's just pointing out that there exists sufficiently fast and correct algorithms for many problems for most uses. Theoretically optimal isn't always the practically most efficient (the exponential-time algorithms for primality testing work better than the polynomial-time, IIRC). -- Beware of bugs in the above code; I have only proved it correct, not tried it. -- Donald E. Knuth |