Diese Frage kann als eine zentrale Forschungsmotivation der Komplexitätstheorie angesehen werden, und eine Vielzahl der komplexitätstheoretischen Ergebnisse wurde erzielt, um der Lösung des P-NP-Problems näher zu kommen.