I'm studying about Cook-Levin theorem but there is a problem I faced. Cook-Levin theorem shows that any NPTM can be encoded as a boolean formula. About given language $A$, instance $w$, and NPTM $M$ that decides $A$, I understand that when a boolean formula $φ$ is true when $M$ accepts $w$ and false when $M$ rejects $w$, decision problem $w∈A?$ will be the same problem as $φ=true?$. But I am confused that can we actually certificate existence of reduction from any other NP problem to SAT, with Cook-Levin theorem. I can't make actual Karp reduction to SAT that doesn't picky about where the reduction comes from, so I can't tell that SAT is in NP-Hard. Please help me to understand why conversion to boolean formula can mean SAT's NP-Hardness...
1 Answer
Any language $L$ in NP is decided by some nondeterministic Turing machine $M$. By Cook–Levin, the problem "Does $M$ accept input $x$?" can be decided by constructing a Boolean formula $\varphi_{M,x}$ that is satisfiable if, and only if, $M$ accepts $x$. Hence $L$ reduces to SAT, so SAT is NP-hard.