In Sipser's proof of the cook levin Theorem the move function (phi move) checks whether a given window is legal. For that we must have an exhaustive set of all possible legal windows to verify that a particular window is legal. Can someone help me prove that this exhaustive set is polynomial in nature. Or clarify, if there is no exhaustive set how are we verifying that it is legal in polynomial time.

I know we are equipped with all the transitions of N but since N is an NTM we have to check every possible combination. Please provide insight (a clear description) as to why this can be done in polynomial time.

  • $\begingroup$ Polynomial in terms of the input size. All the other phi (start, accept and cell) i understood how it is polynomial with respect to the input size. The phi_move description states that it checks whether it is a legal window. (An AND of six legal cells). Isn't there many different legal windows to check from. How is this done in polynomial time? $\endgroup$ – Sid Nov 10 '19 at 13:19

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.