Nachweis der Gleichheit zwischen P und NP Komplexitätsklassen
An dieser Stelle ist es nicht bewiesen, dass die P- und NP-Komplexitätsklassen gleich sind oder nicht. Es gibt jedoch mehrere NP-Aufgaben, für die es nicht bekannt ist, ob sie durch einen polynomialen Algorithmus gelöst werden können. Diese Aufgaben werden NP-vollständig genannt. Wenn nachgewiesen wird, dass eine NP-vollständige Aufgabe durch einen polynomialen Algorithmus gelöst werden kann, könnten alle NP-Probleme auch durch polynomische Algorithmen gelöst werden, und P und NP wären gleich. Es gibt jedoch noch keine Beweise, die diese Hypothese bestätigen oder widerlegen könnten. Das Problem der Gleichheit zwischen P- und NP-Komplexitätsklassen (auch bekannt als Over-the-Board in russischen Quellen) bleibt ein offenes Problem in der Algorithmustheorie. Es ist eine der sieben Millennium-Herausforderungen, für die das Clay Mathematic Institute einen Millionen-Dollar-Preis vergeben hat.