I encountered a question in a test I have taken, its was Proof or Disprove question.
Let L∈NP and let Fcl be the Boolean expression that was created by Cook Levin reduction.
It is known that for all X, X∈L <==> Fcl∈SAT.
Now remember φaccept that Cook Levin reduction produce which is part of Fcl.
the claim you need to decide if its true and supply Proof for it or Disprove and supply counter example is:
φaccept=true if and only if in the last configuration in the configuration table that describes the calculation of the Turing machine M on the language L and the input X,W is in Qaccept.
the course books are:
1) T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms,2nd edition.
2) J. Kleinberg and E. Tardos, Algorithm Design
Thank you very much !