P vs NP

The great­est cur­rently open prob­lem in com­plex­ity the­ory and com­puter sci­ence in gen­eral, which talks about the re­la­tion­ship be­tween the class of effi­ciently solv­able prob­lems, \(P\), and the class of prob­lems with eas­ily check­able solu­tions, \(NP\).

It is a ba­sic re­sult that \(P\subseteq NP\). How­ever, we still do not know whether the re­verse im­pli­ca­tion, \(P \supseteq NP\), holds.

A pos­i­tive, con­struc­tive re­sult would have profound im­pli­ca­tions through all the fields of sci­ence and math, not to men­tion the whole of so­ciety.

Children:

Parents:

  • Mathematics

    Math­e­mat­ics is the study of num­bers and other ideal ob­jects that can be de­scribed by ax­ioms.

  • Complexity theory

    Study of the com­pu­ta­tional re­sources needed to com­pute something