Praktyczny algorytm dla szerokiej klasy NP-zupełnej mógłby wpływać nie tylko na kryptografię, lecz także na optymalizację i nauki przyrodnicze, ponieważ problemy NP-zupełne pojawiają się m.in. w programowaniu całkowitoliczbowym i problemie komiwojażera oraz uproszczonych modelach zwijania białek. W matematyce praktyczny algorytm znajdowania krótkich dowodów mógłby zmienić sposób rozwiązywania problemów, bo poprawność formalnego dowodu da się sprawdzić w czasie wielomianowym. Podkreślali to m.in. Gödel w liście do von Neumanna oraz Cook w opisie problemu milenijnego.
Konsekwencje P ≠ NP