Overview

1

Class P is the class of problems that are decidable in polynomial time by a deterministic Turing machine. Class NP is the class of problems for which the correctness of a witness (evidence that the answer is Yes) can be verified in polynomial time when given the witness. Since problems decidable in polynomial time are also verifiable in polynomial time, it is obvious that P ⊆ NP. However, it is not clear whether P is a proper subset of NP. Although there is no proof yet, many researchers believe that P ≠ NP. This conjecture that class P and class NP are not equal is known as the "P ≠ NP conjecture".