# Are the indices of variables in the formula variable?

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.

• 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?
– D.W.
Commented Feb 4, 2023 at 22:09

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, Your notation doesn't match Wikipedia's definition for $T$. I am using Wikipedia's notation.