MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## An Alternative to the Cook-Levin Theorem

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.

-
 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. – Eric Tressler Sep 4 2010 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.

-
This is exactly the kind of thing I was wondering about. – Huck Bennett Sep 4 2010 at 19:59
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 – Peter Shor Sep 9 2010 at 13:02
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 – Kaveh Nov 26 2010 at 4:43
@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. – Peter Shor Nov 26 2010 at 13:54
rjlipton.wordpress.com/2011/03/14/… – Kaveh Mar 15 2011 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!

-
 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. – Emil Nov 25 2010 at 18:46 Fixed. Because of the way the stack exchange software works, you need to type "\\{" – Peter Shor Nov 25 2010 at 18:58 @Peter, thanks! – Emil Nov 25 2010 at 19:43