Non-deterministic Turing Machine — Jemoka Knowledge Base

We have multiple transitions for a state, symbol pair in non-deterministic TMs. the machine may proceed according to several possible transitions 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,

\begin{equation} L = \left\{x \mid \exists y \in \Sigma^{*}, |y| \leq |x|^{k}, V(x,y) \text{ accepts}\right\} \end{equation}

IFF L \in NP We can call the V the polynomial length proof; we can call y the “witness” Proof if L exists, we create an N to guess y of length at most |x|^{k} nondeterministically, run V(x,y) on each (which is polynomial time), and output; this means that L(N) is L if there is an NTM N that decides L (so L \in NP), we define V(x,y) to accept IFF y encodes an accepting computation history of N on x (now, |y| \leq |x|^{k} because N is an NP NTM, and V(x,y) is polynomial because we are just iterating over the computation history) Boolean Formula Satisfiability Boolean formulas are logical expressions, like:

\begin{equation} \phi = \left(\neg x \wedge { y}\right) \vee z \end{equation}

A satisfying assignment is a setting of variables which makes the formula above true. A Boolean formula is satisfiable if there is a true/false setting to the variables that makes the formula true.

\begin{equation} SAT = \left\{\phi \mid \phi\text{ is satisfiable}\right\} \end{equation}

3cnf-formula This is a particular type of satisfiable formula

\begin{equation} \left(x_1 \vee \neg x_2 \vee x_3\right) \wedge\left(x_4 \vee x_2 \vee x_5\right) \wedge\left(x_3 \vee x_2 \vee \neg x_1\right) \end{equation}

\begin{equation} 3SAT = \left\{\phi \mid \phi\text{ is satisfiable and 3cnf}\right\} \end{equation}

We claim that 3SAT \in NP; we can express 3SAT as:

\begin{equation} 3SAT = \left\{\phi \mid \phi\text{ is in 3cnf and $\exists$ a string $y$ \hat{t} encodes an satisfyingly assignment}\right\} \end{equation}

in particular,

\begin{equation} 3SAT-CHECK = \left\{(\phi, y) \mid \phi\text{ is in 3cnf and $y$ is a satisfying assignment}\right\} \end{equation}

is in P. (actually all of SAT is in NP) Time Complexity of Non-deterministic Turing Machines First,

\begin{equation} \text{TIME}(t(n)) \subseteq \text{NTIME}(t(n)) \end{equation}

where \text{NTIME} is the set of languages such that there exists a Non-deterministic Turing Machine which decides the language within t(n) time. accepting accepting on Non-deterministic Turing Machines is a history of N on w such that we have a sequence c_0, …, c_{t} where C_{0} is the start configuration of q_0 w C_{t} is an accepting configuration (we are in an accepting state) each configuration C_{i} yields C_{i+1} accepting in time t means that such a history exists. N has a time complexity of T(n) if for all n, for all inputs of length n and for all histories, N halts in T(n) time. (we can get it to halt for all strings by having a clock, and computing n and stopping T as needed; if n is correct, then we don’t actually change the language that T recognized) non deterministic turing machines are not more powerful than turing machines Theorem: every non-deterministic Turing machine N can be transformed into a Turing machine M that accepts only strings N accepts. (We don’t care about rejection in this case, because “some rejection state” seems odd if there are some that’s not a rejection state) Proof: We pick an ordering of strings over \left\{Q \cup \Gamma \cup \#\right\}^{*}. To check if we accept w with M: for all strings in \left\{Q \cup \Gamma \cup \#\right\}^{*}, check if for D \in \left\{Q \cup \Gamma \cup \#\right\}, and D = C_0 \# … \# C_{k}, if the sequence C_0 … C_{k} is an accepting computation history in N (that is, C_0 is a valid start configuration, and C_{k} is (1) a valid accepting one) that (2) C_{0} corresponds to the string w. If so, accept. (i.e. we precompute paths) clique problem a k clique is a subgraph which is “complete” (all possible edges are connected) with k nodes assume some encoding of graphs (adjacency matricies): the language

\begin{equation} \text{CLIQUE} = \left\{(G, k) \mid G\text{ is undirected with $k$ clique}\right\} \end{equation}

In particular, we claim that \text{CLIQUE} \in \text{NTIME}\left(n^{c}\right) for some c>1. We do this by…. nondeterministically guess a subset S \subseteq V with |S| = k for all pairs of u,v \in S, if (u,v) is not in E, then reject accept this is NP-Complete, see also many, many NP-Complete thins Hamiltonian path problem A Hamiltonian path is a path which goes through an node exactly once

\begin{equation} \text{HAMPATH} = \left\{(G, s,t) \mid G\text{ is directed with path $s,k$}\right\} \end{equation}

this is also \text{HAMPATH} \in \text{NTIME}\left(n^{c}\right) for some c>1. We do this by…. Again find all paths and guess and check: guess a sequence of paths v_1, …, v_{|v|}, etc.