6
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\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
    Commented Sep 4, 2010 at 0:02

2 Answers 2

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ This is exactly the kind of thing I was wondering about. $\endgroup$
    – Huck Bennett
    Commented Sep 4, 2010 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
    Commented Sep 9, 2010 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
    Commented Nov 26, 2010 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
    Commented Nov 26, 2010 at 13:54
  • 1
    $\begingroup$ rjlipton.wordpress.com/2011/03/14/levins-great-discoveries $\endgroup$
    – Kaveh
    Commented Mar 15, 2011 at 0:26
4
$\begingroup$

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!

Improve this answer
$\endgroup$
2
  • $\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
    Commented Nov 25, 2010 at 18:46
  • $\begingroup$ Fixed. Because of the way the stack exchange software works, you need to type "\\{" $\endgroup$
    – Peter Shor
    Commented Nov 25, 2010 at 18:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .