Skip to main content

Cook - Levin Theorem

Around 1971, Cook and Levin independently discovered the notion of \(NP-completeness\) and gave examples of combinatorial \(NP-complete\) problems whose definition seems to have nothing to do with Turing machines. Soon after, Karp showed that \(NP-completeness\) occurs widely and many problems of practical interest are \(NP-complete\). To date, thousands of computational problems in a variety of disciplines have been shown to be \(NP-complete\).

\(SAT\) is the language of all satisfiable \(CNF\) formulae.

Cook-Levin Theorem: \(SAT\) is \(NP-complete\)

Before we go into the proof first we need to define some things

Configuration of a Turing Machine: A configuration of a Turing Machine at any point of time \(t\) is basically the snapshot of the turning machine at that time. It is an ordered pair of the head position, current state, and tape content. Any configuration is initialized and ended with a special symbol, let \(\#\) mark its ending. Then the contents of the tape at the left of the head, then the current state then the content of the cell where the head is pointed and the content of the tape at the right of the head. So if any configuration is like \((\#, w_1,w_2,q,w_3,w_4,w_5,w_6,\#)\) then the head is pointed at 3rd letter in state \(q\) and the content of the tape is \(w_1w_2w_3w_4w_5w_6\)

Computation Tableau of a Turing Machine: It is a table of configurations where form \(i-\)the row to \(i+1-\)the row it follows the turning machine's transition function at time \(i\) on any input \(x\) and the first row is the starting configuration. A tableau is accepting if any in the tableau is an accepting configuration.


Now let's come to the proof of the theorem.

Proof: Let \(L\) be any language in \(NP\). Then there exists a nondeterministic turning machine \(M\) with runtime \(n^k\) and \(L=\mathcal{L}(M)\).

Idea: The idea is to encode the computation tableau of \(M\) on input \(x\), \(|x|=n\) to a boolean formula \(\varphi\) such that there is an accepting configuration iff \(\varphi \in SAT\)


Let \(x=w_1w_2\dots w_n\). Let \(C=Q\cup \Gamma\cup \{\#\}\) where \(Q\) is the set of states of \(M\) and \(\Gamma\) is set of alphabets of \(M\). Since the Turing machine runs for time \(n^k\) it can at most access \(n^k\) space, So the computation tableau will have \(n^k \) rows and \(n^k\) columns. Now the initial configuration is \[(\#,q_0,w_1,w_2,\dots,w_n,\sqcup,\dots,\sqcup,\#)\]Now any cell in the tableau contains a symbol from \(C\). So for each \((i,j)-\)the cell and \(s\in C\) introduce a variable \(x_{i,j,s}\). \(x_{i,j,s}=1\) iff the \((i,j)-\)the cell in the tableau has the symbol \(s\), otherwise \(x_{i,j,s}=0\).


Therefore we can encode the starting configuration as \[\varphi_{start}=x_{1,1,\#}\wedge \left( \bigwedge_{j=2}^{n+1} x_{1,j,w_{j-1}} \right) \wedge \left( \bigwedge_{j=n+2}^{n^k-1} x_{1, j,\sqcup} \right)\wedge x_{1,n^k,\#}\]Now setting \(x_{i,j,s} =1\) corresponds to placing \(s\) in \((i,j)-\)the cell. To obtain a correspondence between an assignment and a tableau, we must ensure that the assignment sets to 1 exactly one variable for each cell. First, we need to ensure each cell has at least one symbol placed in it. We do it by \(\bigvee\limits_{s\in C} x_{i,j,s}\). Now we have to ensure that the cell does not have more than two symbols placed in it. We do it by \(\bigvee\limits_{s,t\in C, s\neq t} (\overline{x_{i,j,s}}\wedge\overline{x_{i,j,t}})\). Hence for each cell, these two conditions both should follow, therefore \[\left(\bigvee\limits_{s\in C} x_{i,j,s}\right) \wedge \left( \bigvee\limits_{s,t\in C, s\neq t} (\overline{x_{i,j,s}}\wedge\overline{x_{i,j,t}})\right)\]There condition should follow for every cell, therefore, we get the second part for our desired boolean function \[ \varphi_{cell}=\bigwedge_{1\leq i,j\leq n^k}\left[ \left(\bigvee\limits_{s\in C} x_{i,j,s}\right) \wedge \left( \bigvee\limits_{s,t\in C, s\neq t} (\overline{x_{i,j,s}}\wedge\overline{x_{i,j,t}})\right)\right]\]

Formula \(\varphi_{accept}\) guarantees that an accepting configuration occurs in the tableau. The formula ensures that \(\varphi_{accept}\), the symbol for the accept state, occurs in one of the cells of the tableau by stipulating that one of the corresponding variables is set to 1. Hence the formula for it is \[\varphi_{accept}=\bigwedge_{1\leq i,j\leq n^k} x_{i,j,q_{accept}}\]


The last part of the formula has to do with the transitions of the Turing machine. Here we use the concept of the window in the computation tableau
\(\boldsymbol{(i,j)-6}\) window in a Computation Tableau: A window in the tableau is a \(2\times 3\) piece with adjacent rows and columns.
A window is legal if it does not violate the transition function of the turing machine. Determining which windows are legal can be done by case analysis. 

Say $\delta(q_1,a)=(q_1,b,R)$ $\delta(q_1,b)=\{(q_2,c,L),(q_2,a,R)  \}$

Hence $$\varphi_{move}=\bigwedge_{1\leq i,j\leq n^k} ((i,j)-6\text{ window is legal})$$

Therefore the final boolean circuit is $$\varphi=\varphi_{start} \wedge \varphi_{cell} \wedge \varphi_{move} \wedge \varphi_{accept}$$ $\blacksquare$


Labels:

Comments

Post a Comment

Popular posts from this blog

Hierarchy Theorems (Time, Space, Alternation)

There are many hierarchy theorems based on Time, Space, Nondeterminism, Randomization etc. Time Hierarchy Theorem (Version 1) : If $f, g$ are time-constructible functions satisfying $f(n) \log f(n)=o(g(n))$, then $$ DTIME(f(n)) \subsetneq DTIME (g(n)) $$ Proof:  Consider the following Turing machine $D$: "On input $x$, run for $f(|x|)\log (f(|x|))$ steps the Universal $TM$ $\mathcal{U}$ to simulate the execution of $M_x$ on $x$. If $\mathcal{U}$ outputs some bit $b \in\{0,1\}$ in this time, then output the opposite answer (i.e., output $1-b$ ). Else output 0.” Here $M_x$ is the machine represented by the string $x$.      By definition, $D$ halts within $f(n)\log (f(n))$ steps and hence the language $L$ decided by $D$ is in $DTIME(g(n))$. Claim:  $L \notin$ DTIME $(f(n))$ Proof:  For contradiction's sake, assume that there is some $TM$ $M$ and constant $c$ such that $TM$ $M$, given any input $x \in\{0,1\}^*$, halts within $cf(|x|)$ steps and outputs $D(x)$.      The time to si
1 comment
Read more

Function Automata: A Technique to Solve Finite State Automata Problems

Here I will describe a strategy or technique to solve some finite state automata problems. This strategy was first taught to us by my Theory of Computation Professor. The term 'Function Automata' is given to me since we use function-like structures in this.     Suppose you are given a language that is a regular set \(L\). So there exists a \(DFA\) for \(L\), \(L_D=(Q,\Sigma,\delta, q_1, F)\) where \(Q\) is the set of states, \(\Sigma\) is the set of alphabets, \(\delta\) is the transition function, \(S\) is the starting state and \(f\) is the set of final states. Now let \(Q=\{q_1,q_2,\dots,q_n\) where \(n\in\mathbb{N}\). Now we will do a kind of subset construction but every new state will have \(n\) states of \(Q\) but they can repeat. So $$(\underbrace{q_1,q_1,\dots,q_1}_{n\text{ times}})$$ is a state of the new automata. Now, what is the meaning of these new states? Let \(f=(q_{k_1},q_{k_2},\dots,q_{k_n})\) be a new state where \(q_{k_i}\)'s are not necessary to be diff
Post a Comment
Read more