Znaczenie Rozwiązanie problemu miałoby daleko idące konsekwencje dla informatyki teoretycznej i wielu zastosowań. Jego znaczenie wynika z tego, że wiele naturalnych zadań optymalizacyjnych, logicznych i kombinatorycznych można wyrazić jako problemy w NP albo przez redukcje powiązać z problemami NP-zupełnymi. Matematyk Stephen Smale umieścił pytanie „czy P = NP?” jako trzecie na swojej liście problemów matematycznych na XXI wiek (1998) i nazwał je „darem informatyki dla matematyki”. Zaliczył je wówczas – obok hipotezy Riemanna i hipotezy Poincarégo – do trzech jego zdaniem największych otwartych problemów matematyki.

Konsekwencje P = NP Dowód P = NP, zwłaszcza gdyby prowadził do praktycznych algorytmów, mógłby radykalnie zmienić optymalizację, automatyczne dowodzenie twierdzeń, projektowanie algorytmów i kryptografię. Samo formalne P = NP nie musiałoby oznaczać złamania współczesnej kryptografii, bo dowód mógłby nie dawać użytecznego algorytmu, jednak efektywny algorytm dla problemów NP-zupełnych miałby poważne konsekwencje.