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: Patricia Shanahan on 19 Dec 2009 08:01 RussellE wrote: > 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. I have a lot of trouble with understanding what you mean by this. Many problems in NP do not involve variables at all. You cannot depend on the normal proof that SAT is NP-complete because it depends on the lack of an upper bound on the number of variables in a SAT instance. > 2) Some classes of NP problems, like 2SAT > and Horn clauses, have polynomial algorithms. P is definitely a non-empty subset of NP. That seems equally consistent with "P is a non-empty proper subset of NP" and "P is equal to NP". Patricia
From: tchow on 19 Dec 2009 13:00 In article <9788de9a-4f4f-4028-b833-170c195cd88e(a)f18g2000prf.googlegroups.com>, RussellE <reasterly(a)gmail.com> wrote: >3) We can pretty much prove P=NP for >AVERAGE case complexity. No, we can't. It's a little tricky to define average-case complexity correctly, because one has to specify a probability distribution over instances. However, people have figured out the right definitions and proved that there exist complete problems. http://www-cse.ucsd.edu/~russell/average.ps The complete problems are unsatisfactory, however, in that they are not very "natural." It remains a major open problem to prove the completeness of any "natural" problem with a "natural" probability distribution. And of course, whether the complete problems can be solved in polynomial time on average remains wide open. Note, of course, that by carefully constructing a probability distribution that avoids all the "hard" instances, we can easily contrive to solve an NP-complete problem quickly on average. But this doesn't prove that *all* NP problems with arbitrary (non-contrived) probability distributions can be solved quickly on average, which is what "P = NP for average-case complexity" means. >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 It would be nice if we could find any *subexponential* bound for SAT, e.g., 2^(sqrt(n)). -- 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: Tim Little on 19 Dec 2009 19:41 On 2009-12-19, RussellE <reasterly(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? No, and if you had the slightest clue what you were talking about you wouldn't need to ask. - Tim
From: Tim Little on 19 Dec 2009 20:02
On 2009-12-19, RussellE <reasterly(a)gmail.com> wrote: > Reasons P = NP might be true: > > 1) We can prove P=NP for any fixed number of variables. That is not correct; it is not even wrong. It makes no sense. > 2) Some classes of NP problems, like 2SAT and Horn clauses, have > polynomial algorithms. Again, showing you have no clue what P=NP means. All problems in P are in NP, by definition. Showing that P is not empty is not any sort of evidence that P=NP! > 3) We can pretty much prove P=NP for AVERAGE case complexity. No, we cannot. For example, consider the problem of factoring semiprimes. Is there an algorithm with average polynomial running time? (Technically the P=NP question concerns decision problems. To be pickier, consider the decision problem of whether a semiprime S has a factor less than k for k^2 <= S) - Tim |