…building blocks of Non-deterministic Turing Machine. Two transition functions:
\begin{equation} \delta_{0}, \delta_{1} : Q \times \Gamma^{k} \to Q \times \Gamma^{k-1} \times \qty {L, R, S}^{k} \end{equation}
At every point, apply both of these separate functions/branch on both. Some sequences lead to \(q_{\text{accept}}\), and some others lead to \(q_{\text{reject}}\).
We accept IFF exists any path accepts => we reject IFF all path rejects.
why NP is awesome
“what a ridiculous model of computation!”
- Yes, so that’s why P vs. NP is so frustrating as a problem; if NP is indeed ridiculous, should be able prove P != NP
- verifier formulation of NP
- NP captures many, many important problems: SAT, Hamiltonian path problem, clique problem, etc. etc.
- the notion of NP-Completess: “if any of these problems in \(P\), then all of everything in \(NP\) are in \(P\)”