P vs NP

The greatest currently open problem in complexity theory and computer science in general, which talks about the relationship between the class of efficiently solvable problems, \(P\), and the class of problems with easily checkable solutions, \(NP\).

It is a basic result that \(P\subseteq NP\). However, we still do not know whether the reverse implication, \(P \supseteq NP\), holds.

A positive, constructive result would have profound implications through all the fields of science and math, not to mention the whole of society.



  • Mathematics

    Mathematics is the study of numbers and other ideal objects that can be described by axioms.

  • Complexity theory

    Study of the computational resources needed to compute something