P versus NP
Het beroemdste openstaande probleem van de informatica. Zijn problemen waarvan een oplossing snel te controleren is (NP) ook snel op te lossen (P)? De meesten denken van niet, maar een bewijs ontbreekt. Millennium Prize van 1 miljoen dollar.
Geformuleerd door Stephen Cook (1971). Zou P = NP gelden, dan stortte de cryptografie in (RSA en AES berusten op aannames over rekenkundige hardheid). NP-volledige problemen (handelsreizigersprobleem, SAT, knapzakprobleem): wie er één snel oplost, lost ze allemaal op. Praktisch gevolg: we aanvaarden dat sommige problemen "moeilijk" zijn en gebruiken heuristieken en benaderingen (simulated annealing, genetische algoritmen, LP-relaxatie). Quantumcomputers verleggen de grens niet: BQP is een andere complexiteitsklasse.