What is the complexity class of problems that can be solved by a non-deterministic Turing machine in polynomial time?
Show answer
NP
NP stands for Nondeterministic Polynomial time. A key property of NP problems is that while they may be hard to solve, a proposed solution can be verified in polynomial time.
Also asked as:
- What complexity class consists of problems solvable in polynomial time by a non-deterministic Turing machine?