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 18 Dec 2009 19:59 In article <cf7e961f-e6a8-41ff-a22b-e54843b9c091(a)13g2000prl.googlegroups.com>, RussellE <reasterly(a)gmail.com> wrote: >If my algorithm is O(n^10), there is a big difference between >307^10 and 4096^10. Of course, I can always hope the >computers keep getting faster. > > >Russell >- 2 many 2 count "2 many 2 count" must refer to the number of your non sequiturs. -- 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 20:16 On Dec 18, 4:58 pm, tc...(a)lsa.umich.edu wrote: > In article <bde98507-fb9f-4a37-8d0f-7d95aa57e...(a)u16g2000pru.googlegroups..com>, > > RussellE <reaste...(a)gmail.com> wrote: > >Assume I create every 3SAT instance with 10 variables and > >run all of them through a commercial SAT solver. > >I find the hardest instance required 293,142 steps. > >Would this prove P=NP because the worst case > >instance required O(10^5) steps? > > That question is not even wrong. The OP asked why I put "polynomial" in quotes. Assume I have a solver that simply tries every possible assignment. This algorithm solves any 10 variable instance in, at most, 1024 steps or O(n^4). It solves any 11 variable instance in O(n^4) steps. In fact, for any fixed number of variables, my algorithm solves any instance with that many variables in "polynomial" time. Of course, the "polynomial" grows as the number of variables grows. Even so, this simple algorithm proves P=NP for any fixed number of variables. Russell - 2 many 2 count
From: Joshua Cranmer on 18 Dec 2009 21:18 On 12/18/2009 07:58 PM, tchow(a)lsa.umich.edu wrote: > I don't know if Joshua Cranmer is still tracking this thread, but if you > are, what do you think of Russell's understanding of P = NP versus Phil's > understanding, given what Russell says here? I said 'perhaps.' I tend not to dwell too much in this newsgroup, so I have a very poor sense of recurring posters. Extrapolation is always fraught with problems. -- Beware of bugs in the above code; I have only proved it correct, not tried it. -- Donald E. Knuth
From: tchow on 18 Dec 2009 22:50 In article <2989ba22-9721-4cfd-82de-30dd4dd2ff64(a)x25g2000prf.googlegroups.com>, RussellE <reasterly(a)gmail.com> wrote: >this simple algorithm proves P=NP for >any fixed number of variables. And that answer is not even wrong. -- 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 19 Dec 2009 00:11
On Dec 18, 7:50 pm, tc...(a)lsa.umich.edu wrote: > In article <2989ba22-9721-4cfd-82de-30dd4dd2f...(a)x25g2000prf.googlegroups..com>, > > RussellE <reaste...(a)gmail.com> wrote: > >this simple algorithm proves P=NP for > >any fixed number of variables. > > And that answer is not even wrong. The original poster asked if there was any evidence P = NP might be true. I know most people think P =/= NP. I am not one of those people. I won't be too surprised if someone does prove P =/= NP, but history is full examples where most people were wrong about some proof. Reasons P = NP might be true: 1) We can prove P=NP for any fixed number of variables. 2) Some classes of NP problems, like 2SAT and Horn clauses, have polynomial algorithms. 3) We can pretty much prove P=NP for AVERAGE case complexity. The best upper bounds we currently have on complexity may be exponential, but they are still quite low. It would be nice if we could find a polynomial bound, but a proof of P=NP might not give us much of an improvement over existing methods. Theorist are always interested in worst case. The people that actually use this stuff are usually more interested in average case. (except cryptographers). Right at the moment, I think the speed of our computers is more of a limiting factor on the size of problems we can solve than the lack of "good" algorithms. Russell - 2 many 2 count |