5.1 Cook-Levin Theorem

P and NP

A deterministic TM has time constraints T(n) if for every input w with , the TM halts (whether or not it accepts w) in no more than T(n) steps.

We say nondeterministic TM has time complexity T(n) if for every input w with , the TM can halt on w in an accept state, if TM accepts w in no more than T(n) steps.