# Why the Cook-Levin reduction is not a parsimonious reduction?

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.