Timeline for An Alternative to the Cook-Levin Theorem
Current License: CC BY-SA 2.5
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 15, 2011 at 0:26 | comment | added | Kaveh | rjlipton.wordpress.com/2011/03/14/levins-great-discoveries | |
| Nov 26, 2010 at 13:54 | comment | added | Peter Shor | @Kaveh: the universal search problem in Levin's paper is essentially the definition of NP. So the question is which of his other six problems he derived from the universal search problem. SAT/TAUT is third on this list. The tiling problem is sixth on the list. I wouldn't be surprised if Levin had found a reduction directly from the definition of NP-completeness for all of these. | |
| Nov 26, 2010 at 13:36 | history | edited | Peter Shor | CC BY-SA 2.5 |
I noticed the tiling problem is indeed in Levin's original paper. Oops.
|
| Nov 26, 2010 at 5:04 | comment | added | Kaveh | So I think none of them mention SAT as the master problem explicitly (although I think Steve's proof of completeness of TAUT includes NP-completeness of SAT w.r.t. polytime many-one reductions, probably Levin's proof does also). | |
| Nov 26, 2010 at 4:55 | comment | added | Kaveh | I think Levin's paper (the original Russian version) is submitted in 1972 and his master problem seems to be the universal search problem. | |
| Nov 26, 2010 at 4:49 | comment | added | Kaveh | and he mentions that he was not able to add Primes and Graph-Iso to that list. He does not mention SAT (but as I said that is equivalent to TAUT under Cook reductions) and proves that TAUT is NP-complete under Cook-reductions and mentions that proving that TAUT is not in P will be a major breakthrough in complexity theory. | |
| Nov 26, 2010 at 4:43 | comment | added | Kaveh | Domino/Tiling problem is used as intermediary step in one of Kahr/Moore/Wang papers on computability theory to get an improved version of Turing's result that halting can be described as a logical formula. Steve was using Cook-reductions (polytime computable Turing reductions) and not Krap-Lipton reductions (polytime many-one reductions), so TAUT and SAT are reducible to each other. He was mainly concerned with theorem proving and his paper showed that the following problems are of the same polynomial degree: TAUT, DNF-TAUT, 3DNF-TAUT, k-Clique, SubGraph-Isomorphism | |
| Nov 14, 2010 at 13:41 | history | edited | Peter Shor | CC BY-SA 2.5 |
fixed incorrect rumor I heard about Levin's original paper on the Cook-Levin theorem
|
| Sep 9, 2010 at 13:02 | comment | added | Peter Shor | This tiling problem actually gives a fairly clean "first" reduction for the Cook-Levin theorem. I don't know if there's a good place to read about it ... Levin's "Average-case complete" paper is so short that it is very difficult to follow, and his original paper proving the Cook-Levin theorem is not only in Russian, but is also very likely to suffer from the same shortness problem. My suggestion would be to search for a clean exposition of Levin's average-case complete result. Alternatively, you could look at Levin's paper, and use it as a guide to try to figure out this reduction yourself | |
| Sep 4, 2010 at 19:59 | vote | accept | Huck Bennett | ||
| Sep 4, 2010 at 19:59 | comment | added | Huck Bennett | This is exactly the kind of thing I was wondering about. | |
| Sep 4, 2010 at 13:44 | history | edited | Peter Shor | CC BY-SA 2.5 |
changed terminology from "first" to "master"
|
| Sep 4, 2010 at 13:26 | history | answered | Peter Shor | CC BY-SA 2.5 |