Die P=NP-Frage ist nur eine von vielen ungelösten Fragen in der Komplexitätstheorie, doch vielleicht die bedeutendste.

Praktisch glaubt niemand, daß P = NP ist, und es sind beträchtliche Anstrengungen unternommen worden, um das Gegenteil zu beweisen, doch dies bleibt ein ungelöstes, offenes Problem für die Informatik.

The question of whether P = NP become the biggest open question in computing and mathematics. No one knows. That no one in any field of science, engineering, or commerce has ever found a fast algorithm for any of these 3000 problems suggests empirically that P 􀀁 NP. In our current state of knowledge all those hard problems are hard and there is little hope anyone will find a way to solve them quickly.

Die P=NP-Frage ist offen, seitdem sie 1971 von Cook und Levin gestellt wurde. Sie gilt als eines der schwierigsten ungelösten Probleme in der Informatik, ist aber sicherlich das faszinierendste und wichtigste. Entweder können alle diese interessanten und in Anwendungen entscheidenden Probleme gut durch Computer gelöst werden oder überhaupt keines. Außerdem braucht man nur über eines von ihnen Klarheit zu erlangen, um die ganze FrageStellung zu beenden. Außergewöhnliche Forschungsanstrengungen sind unternommen worden, um dieses Problem zu lösen, doch bislang ohne Erfolg.