P equals NP

Definition

P equals NP

The statement $\mathrm{P}=\mathrm{NP}$ asserts that every decision problem in NP also belongs to P:

$$\mathrm{P}=\mathrm{NP}⟺\forall \Pi \in \mathrm{NP}:\Pi \in \mathrm{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, $\mathrm{P}\subseteq \mathrm{NP}$, is already known.

Whether this equality holds is an open problem; it has been neither proved nor disproved.