Talk:Cook-Levin theorem

From Wikipedia, the free encyclopedia

My proof in this article differs from the one given by Garey and Johnson. My Boolean expression B contains the disjunction of the possible transitions for a tape position/computation step (thus requiring at least one transition), whereas the G&J proof contains the conjunction (thus requiring all transitions, which seems wrong). See the definition of group G6, page 43 of the 1997 edition. I think this is a trivial mistake on G&J's part as G&J make it clear what they mean in the table on page 42. But I would appreciate someone to check my working. Gdr 21:00, 2004 Jul 21 (UTC)

Isn't the first sentence under "Definitions" in the Cook's Theorem page wrong? Shouldn't it read as follows: "A decision problem is in NP if a deterministic Turing machine can verify a proposed solution of the decision problem in polynomial time. Equivalently, a decision problem is in NP if a non-deterministic Turing machine can solve the decision problem in polynomial time." This is more consistent with the definitions on the "NP" page. Rodney Topor 04:59, 29 October 2006 (UTC)

Contents

[edit] Merge

I agree that the Proof that Boolean satisfiability problem is NP-complete page should be merged into the Cook's Theorem page. There already is a proof in the the Cook's Theorem page that is more concise, more precise, and more complete. The other proof ignores the polynomial-time requirement of the reduction. I would go further and recommend the "Proof" page be deleted as it is redundant. Rodney Topor 05:47, 29 October 2006 (UTC)

I was poking around on Leonid Levin's page and noticed there is also an article titled Cook-Levin Theorem, which I think should also be merged into here. Note the capital "T" - currently Cook-Levin theorem (small "t") is a redirect, but the capital T page is not. I haven't checked out all of the differences yet, but I will try and move some over if I have time. --Culix 08:39, 10 December 2006 (UTC)

Yay. The theorems are the exact same, and the correct name of the Article should be the Cook-Levin theorem, because even though Cook discovered it first, Levin independently discovered it on the USSR front, and I think some credit should be given to him and to the discoveries he made in that part of the world. Can anyone edit this to make them look nice together??? Charlesblack 16:26, 16 December 2006 (UTC)

Support as per above. Either This article and Proof that Boolean satisfiability problem is NP-complete should both be merged into Cook-Levin Theorem, or Cook's theorem and Cook-Levin theorem should both be merged into Proof that Boolean satisfiability problem is NP-complete. "Cook's Theorem" is an unacceptable title as it does not give the theorem's creators equal merit for their work. However, the proof on this page is certainly the more concise one and should form the bulk of the future article's structure. Allispaul 12:28, 5 March 2007 (UTC)

Support. I think we should merge everything from Cook's theorem and Proof that Boolean satisfiability problem is NP-complete into Cook-Levin theorem, to give proper credit, and keep the most concise proof as the main bulk of the article. Cook-Levin theorem will have to be changed from a redirect into an actual page, and this page will have to be changed to a redirect. Cook-Levin Theorem (capital 'T') will have to be merged into Cook-Levin theorem (small 't') as well (and then turned into a redirect). --Culix 20:46, 7 March 2007 (UTC)

Strong oppose Cook was the first, and the theorem is known by his name all over the world. `'Míkka>t 21:01, 27 November 2007 (UTC)

[edit] Merge complete

I moved this article to Cook–Levin theorem and turned the other two articles into redirects. I decided not to merge any content: Proof that Boolean satisfiability problem is NP-complete had essentially the same proof presented here but in a slightly less systematic way, while Cook-Levin Theorem had a less direct proof. If someone cares enough about these alternative presentations of the proof then they can add them as extra sections. Gdr 13:40, 8 May 2007 (UTC)

Thanks Gdr, it looks great. --Culix 15:08, 19 June 2007 (UTC)

I agree with Culix, Charlesblack, Allispaul, and Gdr. In modern literature, the name Cook-Levin Theorem is only slightly more common than Cook's Theorem: see http://scholar.google.com/scholar?as_epq=%22Cook%27s+Theorem%22&as_ylo=2000 http://scholar.google.com/scholar?as_epq=%22Cook-Levin+Theorem%22&as_ylo=2000 http://www.claymath.org/millennium/P_vs_NP Still, it is more accurate and neutral, so the move to Cook-Levin Theorem was right. --Svnsvn 16:51, 2 November 2007 (UTC)

I agree that the proper name of the theorem is Cook-Levin theorem. Cook and Levin had basically no way of knowing that the other was developing the same idea. Also, both developed it in slightly different ways (Cook asked whether a solution exists; Levin asked what the solution was). Both are interesting and noteworthy.
Levin published only two years after Cook, which at that moment in mathematics, was simultaneous. I have seen a few other theorems or ideas commonly named after two people who developed it in "parallel", but who published many years apart. For example, I have been working on an article about Szasz-Mirakyan operators where the gap between Szasz' and Mirakjan's paper was 9 years. Again, this is "simultaneous" for the time period.
One cannot use Google Scholar to accurately search for the proper name of something unless you also run the search in Russian. Levin was Russian and his paper was seen by Russians. His name will probably need to be the Russian one in the search, too.
« D Trebbien (talk) 16:52 2008 January 4 (UTC)

[edit] Rename was reverted

User:Mikkalai moved the page back to Cook's theorem with no discussion here. I've undone that for the moment. Let's go over the arguments again. Gdr 12:59, 30 November 2007 (UTC)

User:Mikkalai moved the page (again!) to Cook-Levin theorem with no discussion here. (He or she moved it to CookLevin theorem first, which had the side-effect that a non-administrator would have been unable to move it back, but I prefer to hope that that was a mistake rather than deliberate obfuscation.) WP:MOSDASH#Dashes says that the en-dash is to be preferred for linking names (cf. Michelson–Morley experiment, Knuth–Morris–Pratt algorithm etc). Again, if there's an argument, let's consider it. Gdr 15:08, 19 January 2008 (UTC)

[edit] Dtrebbien - the two statements are *exactly* equivalent!

Re the revert by User:Dtrebbien, it should be pointed out that "solvable by a nondeterministic Turing machine in polynomial time" is exactly equivalent to "verifiable by a deterministic Turing machine in polynomial time", and the proof is textbook material. In fact, as the article on NP (complexity) states: The two definitions of NP as the class of problems solvable by a nondeterministic Turing machine (TM) in polynomial time and the class of problems verifiable by a deterministic Turing machine in polynomial time are equivalent. The proof is described by many textbooks, for example Sipser's Introduction to the Theory of Computation, section 7.3.

It is really a matter of personal preference whether one goes with "verifiable in polynomial time by a deterministic Turing machine" or "solvable in polynomial time by a nondeterministic Turing machine". However, keep in mind that the current statement in the article reads: SAT is intuitively in NP because a nondeterministic Turing machine can, in polynomial time, guess an assignment of truth values to the variables, determine the value of the expression under that assignment, and accept this if the assignment makes the entire expression true.[vague]. Many of my students have initially equated "nondeterministic Turing machine" to "guess-and-check", which leads to trouble since a guess-and-check approach for a difficult but satisfiable SAT instance in N variables should take an expected time around half of 2^N, with worst case around 2^N. My recommendation here would be to go with the "verifiable in polynomial time" statement for purposes of effective pedagogy, because it is intuitively obvious even for beginners that calculating the value of a Boolean expression with N variables and M gates should take no more time than evaluating each gate's result in sequence and storing the result. -- Brhaspati\talk/contribs 23:19, 6 April 2008 (UTC)

Based on the above reasons, I've reverted the revert, but kept both the definitions in the article. -- Brhaspati\talk/contribs 23:27, 6 April 2008 (UTC)
Hi Brhaspati,
I didn't like the idea of a non-deterministic Turing machine as "guess-and-checker", either, which is why {{vague}} was there in the first place.
Thanks for providing a reference for a proof that the two classes are equivalent, as it has been something that was alluded to in several sources, but which never seemed to be stated as a defining characteristic.
« D. Trebbien (talk) 04:42 2008 April 7 (UTC)