So I have been reading this: https://people.cs.umass.edu/~immerman/book/ch7.pdf

I do not understand the proof of theorem 7.16, which says that SAT is complete for NP via first-order reductions. My main problem is, that I do not understand the details of the construction of the boolean formula $\gamma(\mathcal{A})$.

Why is the mapping from $ \mathcal{A}$ to $\gamma(\mathcal{A})$ a $t+1$-ary first order query?

I feel like the construction of the first-order reduction isn't explained in much detail and wonder if someone could elaborate more on how the first-order reduction is constructed.

  • $\begingroup$ ${\cal A}$ is mapped to a structure that encodes a SAT-formula. The elements of this structure represent clauses, as well as variables (see Example 2.18). The clauses can be represented by (t+1)-tuples over $A$: t componentes for $\vec e$ and one for $j$. The assumption seems to be that this is at least as large as k and the $a_i$, because this is the arity needed for elements that encode variables. Since $\psi$ is a fixed formula, the definition of $P$ and $N$ by first-order formulas should be straightforward, if tedious. Does this help? $\endgroup$
    – Thomas S
    Jun 29, 2018 at 10:50


Your Answer

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