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.