In the textbook Arora-Barak, after presenting the Cook-Levin theorem's proof the authors say that the proof can be modified slightly to make the reduction parsimonious. The parsimonious reduction is one in which certificates of an NP language are mapped bijectively on the certificates of SAT. I am not sure why the reduction is already not parsimonious.

The reduction basically converts the snapshots $Z_1, Z_2, \dots, Z_{T(n)}$ ($Z_i$ contains the state, the symbols of the two tapes currently under head in the $i$th step) of an oblivious NP machine into a SAT formula, where $T(n)$ is the runtime of the NP machine. The main observation used for converting the sequence of snapshots into a SAT formula is that every $Z_i$ is a function of previous $Z_i$s.

Following is Cook-Levin's proof from Arora-Barak.

enter image description here


1 Answer 1


The string $u$ is the certificate for $x$ with respect to $L$ and $M$, while the string $y \circ z$ is the certificate for $\phi_x$ with respect to $SAT$ and a verifier TM for SAT. $M$ is an oblivious deterministic TM with two tapes - an input tape and a work/output tape. Although I did not find this clearly stated anywhere, it seems reasonable to assume that the output of $M$ is 1 if the final state is $q_{halt}$, and the contents of the output tape are $1 \Box \Box \ldots$, and the heads are positioned at their initial locations at the left ends of the tape. In Garey and Johnson, the formalization of the Turing machine contains two halt states $q_Y$ for accept, and $q_N$ for reject, all other states are designated non-halting - using such a formalization could simplify this reduction; however, Arora and Barak have kept things more general by not focussing on Boolean functions, since the scope of their text is larger.

Any certificate $u$ can be mapped to some certificate $y \circ z$ such that $y = x \circ u$, and $z$ equals the snapshots of $M$ - this map is clearly injective. Similarly, $y \circ z$ may be mapped to $u$ by extracting the appropriate substring - in this case, let us prove that the map is injective. Assume that two certificates $y_1 \circ z_1$ and $y_2 \circ z_2$ may be mapped to the same certificate $u$. This implies that $y_1 = y_2 = x \circ u$, which in turn implies that $z_1 = z_2$ since these strings record the $T(n)$ snapshots of the deterministic TM $M$ starting for the same input $y_1 = y_2$. Given these two injective maps, we can infer that the two sets of certificates have the same cardinality, and hence the reduction is parsimonious.

However, the authors seem to think otherwise. Excercise 2.13.a asks the reader to make the reduction parsimonious, and even a hint is provided:

"Modify the machine M so that it clears up its work tape before outputting a 1 and moves both heads to one end of the tape. Then the final snapshot and head locations are unique."

Note that the suggested modification does not affect the reduction at all! Using our definition of output, we are already assuming that $M$ is doing everything the hint suggests. The only issue I can see is that Condition (4) only examines the last snapshot $z_{T(n)}$ to determine whether the output was 1 but $z_{T(n)}$ only captures a small portion of the output tape - I would question whether this is an accurate test for whether $M$ halted and produced the output 1 - that is, I am not sure that the reduction given in the text is correct.


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.