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: Tim Little on 18 Dec 2009 17:47 On 2009-12-18, RussellE <reasterly(a)gmail.com> wrote: > We can define the words "worst case complexity". But, there is no > "worst case complexity" 3SAT instance. You have a severe misunderstanding. "Worst case complexity" is defined relative to an algorithm, not an instance. > Any solvable 3SAT instance can be solved in polytime using the right > solver. Any instance of 3SAT whatsoever can be decided in a single step. Once again, complexity is *not* a property that applies to an instance. > We might already have such an algorithm. We do not. All known algorithms have cases where the runtime is not polynomial. > The P=NP problem is to PROVE the algorithm decides all 3SAT > instances in a polynomial number of steps. No, it is to prove that *there exists* such an algorithm, whether we actually find one or not. > In fact, I am curious if anyone has done any research in this area. Of course they have! - Tim
From: tchow on 18 Dec 2009 17:52 In article <slrnhio1jo.n6v.tim(a)soprano.little-possums.net>, Tim Little <tim(a)little-possums.net> wrote: >On 2009-12-18, RussellE <reasterly(a)gmail.com> wrote: >> We might already have such an algorithm. > >We do not. All known algorithms have cases where the runtime is not >polynomial. Technically, we don't *know* this. There are algorithms that are so complicated that we can't actually prove that they don't run in polynomial time on all instances. And as Phil mentioned, we can even construct an artificial algorithm with the property that proving that it doesn't solve SAT in polynomial time would prove 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: RussellE on 18 Dec 2009 19:53 On Dec 18, 4:03 am, Ben Bacarisse <ben.use...(a)bsb.me.uk> wrote: > RussellE <reaste...(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. Yes, worst case complexity refers to an algorithm, not an instance. Even so, many proofs of bounds on complexity create particular instances that requires an exponential number of steps for a specific algorithm to solve. If someons does prove P=NP it will probably be several algorithms with a "master" algorithm that determines which other algorithms to use based of the particular instance. There are already algorithms that use case by case analysis of the instance to come up with a more efficient algorithm. > >> "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. My point is it is harder to prove bounds for a algorithm than it is to come up with an algorithm that works well in practice. One example would be restarts. Many commercial SAT solvers use restarts, yet, I haven't read any papers that put bounds on DPLL solvers using restarts. > > 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. 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? Russell - 2 many 2 count
From: RussellE on 18 Dec 2009 19:56 On Dec 18, 8:49 am, tc...(a)lsa.umich.edu wrote: > >307-digit key crack endangers 1024-bit RSA > >http://arstechnica.com/old/content/2007/05/researchers-307-digit-key-... > > 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. 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
From: tchow on 18 Dec 2009 19:58
In article <bde98507-fb9f-4a37-8d0f-7d95aa57e6bf(a)u16g2000pru.googlegroups.com>, 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? That question is not even wrong. 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? -- 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 |