Non-deterministic Polynomial Time (NP)

Non-deterministic Polynomial time (NP): a language $L$ is said to be solvable in non-deterministic polynomial time if there exists an NDTM s.t.:

• $M$ accepts $L$
• $T_M(n)\in O(n^k)$ is eventually dominated by a polynomial function

We can define $NP$ in the same way.