…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!”

NFA is a relaxation of DFA, but which is allowed to make non-deterministic “verified guesses”.

this is basically a DFA, but our new machine accepts a string if there exists some path that reaches some accept state from some start state.

at each state, we can have any number of out arrows for some letter \(\sigma \in \Sigma\), including for the empty string \(\varepsilon\). meaning we can move between states without doing anything.

Non-Deterministic Space is like Non-Deterministic Computation but now is space efficient.

requirements

We say \(A \in \text{NSPACE}\qty(s \qty(n))\) if \(\exists\) Non-deterministic Turing Machine \(M\) which decides \(A\) such that \(M\) always uses \(O\qty(s \qty(n))\) space.

additional information

See NL

We have multiple transitions for a state, symbol pair in non-deterministic TMs.

1. the machine may proceed according to several possible transitions
2. the machine accepts an input if there exists an accepting computation history for the machine on the string

Here’s the

basically a turing machine except the transition is a subset instead of a single transition.

\(L\) is in \(NP\) IFF there are polynomial-length proofs (“witnesses”) that can be decided efficiently for membership in \(L\)

There exists some constant \(k\) and a polynomial-time Turing-machine \(V\),