en klass av matematiska problem som kan vara svåra att lösa, men som har lösningar som det är lätt att kontrollera. – När det gäller matematisk komplexitet talar man om de tre klasserna P, NP och de NP‑fullständiga problemen. – Klassen NP omfattar också klassen P, som består av de mest hanterliga problemen, men oftast menar man med NP bara de problem som inte också ingår i P. (Se också frågan om ifall P=NP.) – När man säger att lösningarna går snabbt att kontrollera menar man i relation till problemets svårighetsgrad. Ett enkelt sätt att jämföra svårighetsgraden i olika problem är att räkna hur många tecken som ingår i det matematiska uttryck som beskriver problemet. – Ett exempel på NP‑problem är schemaläggning för gymnasium. Klasser, lärare och lektionssalar ska kombineras så att alla lektioner kan äga rum enligt läroplanen och ingen klass, lärare eller sal dubbelbokas. Det är besvärligt att sätta ihop ett schema, men lätt att kolla ifall det har blivit rätt. Ett annat exempel är att hitta primfaktorerna till mycket stora tal. Att hitta dem är svårt, att kontrollräkna är elementärt. När det däremot gäller problem i den NP‑fullständiga klassen så tar kontrollräkningen i princip lika lång tid som det tog att hitta lösningen. – NP står för non-deterministic polynomial. En förklaring till den benämningen står i i Wikipedia.
[förkortningar på N] [matematik] [ändrad 23 maj 2018]