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.