1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Feb 4, 2023 at 22:09

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ I messed up the notation, corrected that. $\endgroup$ Feb 5, 2023 at 6:05
  • $\begingroup$ @advocateofnone, Your notation doesn't match Wikipedia's definition for $T$. I am using Wikipedia's notation. $\endgroup$
    – D.W.
    Feb 5, 2023 at 6:09
  • $\begingroup$ Changed it to match the wiki $\endgroup$ Feb 5, 2023 at 6:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.