Back كثير حدود غير قطعي Arabic NP-сложност Bulgarian NP (klasa kompleksnosti) BS NP (Complexitat) Catalan NP (třída složitosti) Czech NP Danish NP (Komplexitätsklasse) German NP (complexity) English NP (clase de complejidad) Spanish NP (پیچیدگی) Persian
NP, de aanduiding voor niet-deterministisch polynomiaal, is een complexiteitsklasse die alle beslissingsproblemen bevat die oplosbaar zijn in polynomiale tijd door een niet-deterministische turingmachine.
In de complexiteitstheorie is NP ook bekend als NTIME( nO(1) )
NP kan ook beschouwd worden als de verzameling beslissingsproblemen (te beantwoorden met 'ja' of 'nee') waarvoor een 'ja'-oplossing in polynomiale tijd geverifieerd kan worden door een deterministische turingmachine. De beslissingsproblemen waarvoor een 'nee'-oplossing eenvoudig te controleren is, behoren tot Co-NP, het complement van NP.