SAT 
OR
If SAT 
OR
for every problem 
OR
SAT 
It can be shown that
i) graph coloring 
NP
ii) SAT 
coloring
graph coloring NPC
Similarly
K-Clique, HC, TSP etc. are also NPC.
Def. NP-hard:
is NP-hard if for all problem 