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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.