Houjun Liu

Non-deterministic Turing Machine

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\),

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

IFF \(L \in NP\)

We can call the \(V\) the polynomial length proof; we can call \(y\) the “witness”


Proof

  1. 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\)
  2. 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 = \qty(\neg x \wedge { y}) \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 = \qty {\phi \mid \phi\text{ is satisfiable}} \end{equation}

3cnf-formula

This is a particular type of satisfiable formula

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

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

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

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

in particular,

\begin{equation} 3SAT-CHECK = \qty {(\phi, y) \mid \phi\text{ is in 3cnf and $y$ is a satisfying assignment}} \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

  1. \(C_{0}\) is the start configuration of \(q_0 w\)
  2. \(C_{t}\) is an accepting configuration (we are in an accepting state)
  3. 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-Polynomial Time

\begin{equation} NP = \bigcup_{k \in N} \text{NTIME}\qty(n^{k}) \end{equation}

Meaning, these are problems with the property that once you “have” the solution, its “easy” to verify the solution.

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 \(\qty {Q \cup \Gamma \cup \#}^{*}\).

To check if we accept \(w\) with \(M\): for all strings in \(\qty {Q \cup \Gamma \cup \#}^{*}\), check if for \(D \in \qty {Q \cup \Gamma \cup \#}\), 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} = \qty {(G, k) \mid G\text{ is undirected with $k$ clique}} \end{equation}

In particular, we claim that \(\text{CLIQUE} \in \text{NTIME}\qty (n^{c})\) 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} = \qty {(G, s,t) \mid G\text{ is directed with path $s,k$}} \end{equation}

this is also \(\text{HAMPATH} \in \text{NTIME}\qty (n^{c})\) 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.