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: tchow on 17 Dec 2009 20:02 In article <hgecas$s51$1(a)news-int2.gatech.edu>, Joshua Cranmer <Pidgeot18(a)verizon.invalid> wrote: >I suspect he understands it, perhaps in greater detail than you do. Just my opinion, but based on my readings of Phil's posts and Russell's posts over the years, I would give Phil the edge. >He's just pointing out that there exists sufficiently fast and correct >algorithms for many problems for most uses. The context was whether we have evidence that P = NP. Pointing out the above fact in that context is a non sequitur. -- 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 18 Dec 2009 00:07 On Dec 17, 1:36 pm, cplxphil <cplxp...(a)gmail.com> wrote: > On Dec 17, 3:21 pm, RussellE <reaste...(a)gmail.com> wrote: > > 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. We can define the words "worst case complexity". But, there is no "worst case complexity" 3SAT instance. Any solvable 3SAT instance can be solved in polytime using the right solver. > > > >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. 307-digit key crack endangers 1024-bit RSA http://arstechnica.com/old/content/2007/05/researchers-307-digit-key-crack-endangers-1024-bit-rsa.ars > "Most instances" is essentially > meaningless. The P = NP problem is to find a single algorithm that > decides *all* SAT instances in polynomial time. We might already have such an algorithm. The P=NP problem is to PROVE the algorithm decides all 3SAT instances in a polynomial number of steps. This could easily be much harder than finding an efficient algorithm. In fact, I am curious if anyone has done any research in this area. For example, has someone generated every possible 3SAT instance with, say, 12 variables, and run them through a commercial SAT solver to see if any of the instances required more than a "polynomial" number of steps to solve? > > 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? Yes, I meant upper bounds. > Have you read and understood Stephen Cook's paper on the P vs. NP > problem? I hadn't read that particular paper. I noticed he mentions the Composite problem. I think the state of the P=NP problem is in a similar state as the Composite problem was before a poynomial algorithm was found. There were efficient, probablistic, "exponential" algorithms, but no one had proven there exists a deterministic, polynomial algorithm. I am not sure what you would consider "evidence". I consider polynomial alogrithms for NP problems like 2SAT to be evidence that P=NP may be possible. History tells us that many probelems that were once considered unsolvable have been solved. Russell - 2 many 2 count
From: Ben Bacarisse on 18 Dec 2009 07:03 RussellE <reasterly(a)gmail.com> writes: > On Dec 17, 1:36 pm, cplxphil <cplxp...(a)gmail.com> wrote: >> On Dec 17, 3:21 pm, RussellE <reaste...(a)gmail.com> wrote: > >> > 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. > > We can define the words "worst case complexity". > But, there is no "worst case complexity" 3SAT instance. > Any solvable 3SAT instance can be solved in polytime > using the right solver. What does that mean? How do you ascribe what is usually an asymptotic bound ("polytime") to a single instance? Unless the algorithm is probabilistic, a solver for a particular instance simply takes a fixed number of steps. >> > > >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. > > 307-digit key crack endangers 1024-bit RSA > http://arstechnica.com/old/content/2007/05/researchers-307-digit-key-crack-endangers-1024-bit-rsa.ars > >> "Most instances" is essentially >> meaningless. The P = NP problem is to find a single algorithm that >> decides *all* SAT instances in polynomial time. > > We might already have such an algorithm. > The P=NP problem is to PROVE the algorithm decides all > 3SAT instances in a polynomial number of steps. > This could easily be much harder than finding an > efficient algorithm. If there is no need to prove that the algorithm works in polynomial time then, yes, finding candidate algorithms is trivial. If you can prove that any one candidate does, in fact, work (in polynomial time) then P = NP. > In fact, I am curious if anyone has done any research > in this area. For example, has someone generated > every possible 3SAT instance with, say, 12 variables, > and run them through a commercial SAT solver to see > if any of the instances required more than a "polynomial" > number of steps to solve? Again, what does this mean. I see now the "quotes" have come in to it so maybe you don't know exactly what you mean either. <snip> -- Ben.
From: tchow on 18 Dec 2009 11:44 In article <01f90c21-0546-4ba3-9591-39c46cf46cb3(a)u36g2000prn.googlegroups.com>, RussellE <reasterly(a)gmail.com> wrote: >We can define the words "worst case complexity". >But, there is no "worst case complexity" 3SAT instance. True; so what? >Any solvable 3SAT instance can be solved in polytime >using the right solver. In fact, it can be solved in constant time. >In fact, I am curious if anyone has done any research >in this area. For example, has someone generated >every possible 3SAT instance with, say, 12 variables, >and run them through a commercial SAT solver to see >if any of the instances required more than a "polynomial" >number of steps to solve? It's not clear what you mean by "polynomial" here. Certainly, one can construct instances on which DPLL provably takes exponential time. DPLL forms the basis for most branching solvers. Of course, modern SAT solvers have complicated refinements to the basic DPLL algorithm, including clause learning, so it is not so easy to construct provably hard instances for them, simply because the algorithm is so complicated. But commercial SAT solvers don't seem to do so well on cryptographic problems. >I am not sure what you would consider "evidence". I'll tell you what I would consider evidence. Come up with an algorithm that appears to break all known cryptographic instances rapidly. Even if you can't prove that your algorithm runs in polynomial time, I would consider that to be pretty good evidence that P = NP. -- 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: tchow on 18 Dec 2009 11:49
Forgot to comment about this: In article <01f90c21-0546-4ba3-9591-39c46cf46cb3(a)u36g2000prn.googlegroups.com>, RussellE <reasterly(a)gmail.com> wrote: >307-digit key crack endangers 1024-bit RSA >http://arstechnica.com/old/content/2007/05/researchers-307-digit-key-crack-endangers-1024-bit-rsa.ars So just bump the size up to 2048 bits or 4096 bits. What does that do? A factor of two or four in the size of the instance shouldn't be a problem for a polynomial-time algorithm. -- 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 |