Nächste Seite: Polynomielle Reduzierbarkeit Aufwärts: NPC Beweise Vorherige Seite: NPC Beweise Inhalt
Die große Frage der Informatiker P=NP oder P
NP?
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.