We have already seen that \(\sc{SAT}\) is in \(\textbf{NP}\). In order to demonstrate Theorem 3.4 it thus suffices to show that all problems \(X \in \textbf{NP}\) are polynomial time reducible to \(\sc{SAT}\). Supposing that \(X \in \textbf{NP}\) there must again be a non-deterministic Turing machine \(N = \langle Q,\Sigma,\Delta,s \rangle\) accepting \(X\) with polynomial time complexity \(p(n)\). The proof of Theorem 3.4 then proceeds by showing that for all inputs \(x\) of length \(n\) for \(