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.
Children:
- P vs NP: Arguments against P=NP
Why we believe P and NP are different
Parents:
- 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