P vs NP
Najsłynniejszy otwarty problem informatyki. Czy problemy, których rozwiązanie da się szybko zweryfikować (NP), da się też szybko rozwiązać (P)? Większość uważa, że nie, ale nikt tego nie udowodnił. Nagroda Milenijna: milion dolarów.
Sformułowany przez Stephena Cooka (1971). Gdyby P = NP, upadłaby cała kryptografia (RSA i AES opierają się na założeniach o trudności obliczeniowej). Problemy NP-zupełne (komiwojażer, SAT, plecak): szybkie rozwiązanie jednego oznacza szybkie rozwiązanie wszystkich. Praktyczna konsekwencja: godzimy się z tym, że niektóre problemy są „trudne”, i stosujemy heurystyki oraz aproksymacje (symulowane wyżarzanie, algorytmy genetyczne, relaksacja LP). Komputery kwantowe nie przesuwają tej granicy — BQP to inna klasa złożoności.