In general to prove that a given problem is NP-complete we show that a known NP-complete problem is reducible to it. This process is possible since Cook and Levin used the logical structure of NP to prove that SAT, and as a corollary 3-SAT, are NP-complete. This makes SAT the "first" NP-complete problem and we reduce other canonical NP-complete problems (e.g. CLIQUE, HAM-PATH) from it.

My question is whether there is a way to prove directly from the definition/logical structure of NP that a different problem (i.e. not SAT) is NP-complete. A friend suggested that it would be possible to tailor the proof of the Cook-Levin Theorem to show that, for example, CLIQUE is NP-complete by introducing the reduction from SAT during the proof itself, but this is still pretty much the same thing.

  • $\begingroup$ The Cook-Levin proof is very short, and the proofs of the reduction of several problems to SAT are also very short -- I don't see how it's in any way indirect to consider the two arguments together. $\endgroup$ – Eric Tressler Sep 4 '10 at 0:02

In his infamously short paper "Average-case complete problems," Leonid Levin uses a tiling problem as the master ("first") NP-complete average-case problem (which means he also automatically uses it as a master NP-complete problem).

UPDATE: Contrary to what I was speculating in my answer previously, in his original paper on the Cook-Levin theorem (I found an English translation linked to from the Wikipedia Cook-Levin theorem article), it's not clear whether Levin uses the tiling problem as a master problem. He lists six NP-complete problems (SAT is number 3, and the tiling problem is number 6), but leaves out the proofs, so it's not completely clear which one is the master problem. Very likely, it was SATISFIABILITY, and so Levin found essentially the same proof as Cook.

  • $\begingroup$ This is exactly the kind of thing I was wondering about. $\endgroup$ – Huck Bennett Sep 4 '10 at 19:59
  • $\begingroup$ 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 $\endgroup$ – Peter Shor Sep 9 '10 at 13:02
  • 1
    $\begingroup$ I think Levin's paper (the original Russian version) is submitted in 1972 and his master problem seems to be the universal search problem. $\endgroup$ – Kaveh Nov 26 '10 at 4:55
  • 2
    $\begingroup$ @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. $\endgroup$ – Peter Shor Nov 26 '10 at 13:54
  • 1
    $\begingroup$ rjlipton.wordpress.com/2011/03/14/levins-great-discoveries $\endgroup$ – Kaveh Mar 15 '11 at 0:26

Yes, for example TMSAT (Turing Machine SAT):

TMSAT = $\{ \langle \alpha, x, 1^n, 1^t \rangle : \exists u \in \{0,1\}^n$ such that $M_\alpha$ outputs 1 on input $\langle x,u \rangle$ within $t$ steps.$\}$

(Theorem 2.9 of Arora-Barak. See Chapter 2 draft: http://www.cs.princeton.edu/theory/index.php/Compbook/Draft#np)

It is quite easy to show that this problem is NP-complete!

  • $\begingroup$ I'm having trouble putting the set brackets (braces) around the 0,1. If anyone knows how to fix it, please let me know, or edit it. $\endgroup$ – Emil Nov 25 '10 at 18:46
  • $\begingroup$ Fixed. Because of the way the stack exchange software works, you need to type "\\{" $\endgroup$ – Peter Shor Nov 25 '10 at 18:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.