Are the indices of variables in the formula variable?

Question

Let $L$ be an arbitrary language in $\Sigma_3$. Thus it can be written that $x \in L \Leftrightarrow \exists y^{p(|x|)} \forall z^{p(|x|)} \exists w^{p(|x|)} \langle x,y,z,w \rangle \in B$ where $p(\cdot)$ is some polynomial function and $B$ is some language in $P$.

While giving a reduction from $L$ to $\Sigma_3$-SAT one uses Cook-Levin's idea to to create a formula $\phi$ s.t. $\phi$ is satisfiable $\Leftrightarrow$ $\langle x,y,z,w \rangle \in B$. But then the indices of variables in $\phi$ depend on $x,y,z,w$, i.e. $\phi$ changes with different values of $x,y,z,w$. Which does not make sense to me. Where am I going wrong ?

To elaborate the linked Cook-Levin proof uses the tableau method which creates new Boolean variables $T_{isj}$ for each cell at index $i,j$ in the tableau, such that $T_{isj}=1$ iff the cell has symbol $s$. While creating the formula $\phi$ one then adds unit clauses $T_{0r_11} \wedge T_{0r_22} \cdots \wedge T_{0r_kk}$ where $r_1r_2\cdots r_k$ is the input string. Hence, the indices of the formula created depend on the input.

• D.W.: Can you elaborate on what formula $\phi$ you have in mind? Why do you think the indices depend on $x$? Are you familiar with the proof of the Cook-Levin theorem?

Answer 1

There seems to be a misunderstanding in the linked proof. If the input is $r_1 \cdots r_k$, then $T_{i,r_i,0}$ will be true for each $i=1,\dots,k$.

If $x_i$ is the $i$th bit of $x$, so that $r_i=x_i$, then we have a clause $x_i \Leftrightarrow T_{i,1,0}$ and $\neg x_i \Leftrightarrow T_{i,0,0}$, both of which are easy to express as CNF clauses. You can do something similar for $y,z,w$.

• advocateofnone: I messed up the notation, corrected that.
• D.W.: @advocateofnone, Your notation doesn't match Wikipedia's definition for $T$. I am using Wikipedia's notation.
• advocateofnone: Changed it to match the wiki