…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 \left\{L, R, S\right\}^{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”