Komplexitetsteori
Grenen av datavetenskapen som klassificerar problem efter hur mycket tid och minne de kräver — inte hur svåra de känns.
Fältet formaliserades av Juris Hartmanis och Richard Stearns 1965, som gav det dess namn och Turingpriset 1993. Problem sorteras i klasser: P är det som går att lösa i polynomisk tid, NP det där en föreslagen lösning går att kontrollera i polynomisk tid, PSPACE det som klarar sig med polynomiskt minne oavsett tid. Klassificeringen gäller problemet, inte den specifika algoritmen — vilket skiljer den från Big-O, som beskriver en given implementation.
Den praktiska nyttan är att veta när man ska sluta leta. Är ett problem NP-fullständigt är det ingen mening att jaga en exakt effektiv algoritm — då byter man till heuristiker, approximationer eller en begränsad problemvariant. Kryptografin lever tvärtom på att vissa problem är svåra: hela publik nyckel-kryptografi vilar på att ingen hittat ett snabbt sätt att faktorisera stora tal.