Definition
P equals NP
The statement
asserts that every decision problem in NP also belongs to P: In other words, every decision problem whose yes-instances have polynomial-length certificates verifiable in deterministic polynomial time can also be solved in deterministic polynomial time. The reverse inclusion,
, is already known. Whether this equality holds is an open problem; it has been neither proved nor disproved.