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.
 A: 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!
A: 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.
