Läßt sich jedes Problem, daß sich
nichtdeterministisch in polynomieller Zeit lösen läßt, auch in
deterministischer polynomieller Zeit lösen?
Allgemein wird angenommen, daß
. Dies ist allerdings nicht bewiesen. An dieser Frage beißen sich Mathematiker und Informatiker seit vielen Jahren die Zähne aus. Es ist eine hohe Belohnung auf die Antwort auf diese Frage ausgesetzt. Es gab schon viele Scheinantworten, die dann doch wieder umgestossen wurden, weil sie nur Spezialfälle waren.