Timeline for Independence of P = NP?
Current License: CC BY-SA 2.5
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 6, 2011 at 14:09 | comment | added | Zirui Wang | @Noah Stein: If you patch it up that way, then "no" instances will take exponential time. | |
| Dec 25, 2010 at 6:23 | comment | added | Zirui Wang | What if the polynomial time algorithm gives the right answer but cannot give a certificate? Levin's algorithm will miss it. | |
| Dec 23, 2010 at 14:54 | comment | added | Noah Stein | Yes, and the definition is that there exists a polynomial time algorithm. It requires neither that we know the algorithm nor that we know the polynomial. You may be interested in the opposite case of the the Robertson-Seymour theorem which says that for any minor-closed family of graphs, there is an algorithm to test membership in the family with cubic runtime in the size of the graph. The theorem is nonconstructive in the opposite way: it doesn't actually give an algorithm, it just tells you how to construct one if you had a finite list of forbidden minors, which exists. | |
| Dec 23, 2010 at 12:28 | comment | added | Zirui Wang | Suppose P = NP. Then this algorithm has a polynomial upper bound. But you may not be able to tell this bound in advance. So it still does not prove the algorithm is polynomial time. It boils down to the definition of polynomial time. In fact it may take infinite time to find the bound. | |
| Dec 23, 2010 at 12:05 | vote | accept | Zirui Wang | ||
| Dec 23, 2010 at 12:13 | |||||
| Dec 21, 2010 at 15:32 | comment | added | Noah Stein | @Mark: Wow, good point. I had somehow failed to notice that. Thanks! | |
| Dec 21, 2010 at 15:31 | comment | added | Noah Stein | @Zirui: This is easily fixed by running any old (not necessarily polytime) algorithm in parallel with the rest and returning the result of that if it completes. | |
| Dec 21, 2010 at 5:51 | comment | added | Mark Lewko | A minor clarification: Levin-type algorithms (which can approximately describe as just running all possible algorithm in parallel) rely on a sub-algorithm producing a polynomial size certificate that can be verified polynomial time. Thus it gives an explicit polynomial time algorithm for NP \cap CoNP (if and only if NP \cap CoNP = P) but not for all of NP. | |
| Dec 21, 2010 at 5:12 | comment | added | Zirui Wang | This algorithm is not even recursive, meaning it halts on all inputs. A polynomial time algorithm must be recursive in the first place. | |
| Dec 21, 2010 at 4:02 | history | answered | Noah Stein | CC BY-SA 2.5 |