Problem $8($Bonus: $30$ points$)$

In this problem, we will prove the Cook$-$Levin theorem.

Theorem $($Cook$,1971$; Levin, $1973).$ SAT is NP$-$complete.

We saw in lecture that SAT is in NP$,$ so it remains to prove that SAT is NP$-$hard, i$.$e$.$ that every problem

in NP is polynomial$-$time mapping reducible to SAT. Let Ain NP$.$ Then we know that there exists a $p-$

time verifier $V$ for $A,$ where $p$ is some polynomial. We will exhibit a polynomial time Turing machine that

computes a mapping reduction from $A$ to SAT. To do this, we will show how to construct a boolean formula

${}_{V,x}$ from the computation of $V$ on input $x$ such that there is a certificate $y$ with which $V$ accepts $x$ iff there

is a satisfying assignment of ${}_{V,x}.$

Let $V=(Q,q_0,q_{\text{a}\text{c}\text{c}\text{e}\text{p}\text{t}},q_{\text{r}\text{e}\text{j}\text{e}\text{c}\text{t}},,,).$ Recall that a verifier is a $2-$tape Turing machine with a read$-$only

second tape called the certificate tape, so

$$:$QQ\{L,R\}.$

Since $V$ is $p-$time, in the computation of $V$ on input xin${}^n$ with certificate $y,$ there will never be more than

$p(n)$ configurations and the work$-$tape head will never move beyond the $p(n)-$th cell on the work$-$tape. The

contents of the work$-$tape on every configuration may therefore be encoded in a $p(n)p(n)$ matrix $C,$ where

the $i$ th row $C_i$ of $C$ consists of the first $p(n)$ cells in the work$-$tape of the $i$ th configuration. Our formula ${}_{V,x}$

will be a conjunction of constraints requiring that $C$ encodes a valid computation of $V$ on $x,$ parameterized

by the certificate $y.$ Before defining our boolean variables, we will make a simplifying assumption that

doesn't lose generality.

Claim $2.$ For any $t-$time verifier $V,$ there is an equivalent $t-$time verifier $V^{\text{'}}$ such that the certificate tape$-$head

always transitions right.

Claim $2$ allows us to assume that the transition from $C_i$ to $C_{i+1}$ is the only transition which depends on the

$y_i.$ We now define the set of boolean variables $V$ of ${}_{V,x}$ as follows. For each iin$[p(n)],$

for each qinQ, we'll have a variable $s_i^q.$ We will encode that the state of configuration $i$ is $q$ by $s_i^q=1.$

for each bin$,$ we'll have a variable $c_i^b.$ We will encode that the $i$ th entry of the the certificate $y$ is $b$

by $c_i^b=1.$

for each jin$[p(n)],$

for each ain$,$ we'll have a variable $t_{i,j}^a.$ We will encode that entry $C_{i,j}($i$.$e$.$ the $j$ th work$-$tape

cell of the $i$ th configuration$)$ contains symbol $a$ by $t_{i,j}^a=1.$

a variable $h_{i,j}.$ We will encode that the work$-$tape head is at cell $j$ on configuration $i$ by $h_{i,j}=1.$

$($a$)(3$ points$)$

Prove Claim $2.$

$($b$)(3$ points$)$

We want to use a set of $l$ boolean indicator variables in to encode an element from a set of size $l$ : e$.$g$.$ we

have one indicator variable $t_{i,j}^a$ for each symbol ain$.$ However,