(Notes from parts of Chapter 15)
Let \(L,Q\) be languages. We say that \(Q\) is polynomial-time reducible to \(L\), written \[Q \leq_p L,\] if there is a polynomial-time computable function \(f\) such that \[x \in Q \iff f(x) \leq L.\]
Theorem 2.5. Let \(R\leq_p Q\) and \(Q \leq_p L.\) Then \(R \leq_p L\).
A language \(L\) is called \(\mathbf{NP}\)-hard if for every \(Q \in \mathbf{NP}\), we have \(Q \leq_p L\).
A language \(L\) is called \(\mathbf{NP}\)-complete if \(L \in \mathbf{NP}\) and \(L\) is \(\mathbf{NP}\)-hard.
Theorem 2.6. There there is an \(\mathbf{NP}\)-complete language \(L\) such that \(L \in \mathbf{P}\), then \(\mathbf{NP} = \mathbf{P}\).
Theorem 3.1 (Cook's Theorem) \(\text{SAT}\) is \(\mathbf{NP}\)-complete.
Theorem 4.1. Let \(Q\) be an \(\mathbf{NP}\)-complete. If \(Q \leq_p L\), then \(L\) is \(\mathbf{NP}\)-hard.