NP (complexiteitsklasse)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/bc/Complexity_classes.svg/250px-Complexity_classes.svg.png)
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.
Definitie
NP kan gedefinieerd worden in termen van NTIME:
- .
In 1974 werd door Ronald Fagin de stelling van Fagin bewezen die stelt dat een beslissingsprobleem in existentiële tweede-orde logica uitgedrukt kan worden dan en slechts dan als het oplosbaar is in polynomiale tijd door een niet-deterministische turingmachine (het behoort dus tot NP). Sindsdien zijn voor andere complexiteitsklassen ook dergelijke stellingen bewezen.[1]
Kenmerken
De complexiteitsklasse P is een deelverzameling van NP; een niet-deterministische turingmachine die geen niet-determinisme gebruikt is namelijk gelijk aan een deterministische turingmachine. De beslissingsproblemen in P behoren dus ook tot NP. Het vermoeden bestaat dat P een strikte deelverzameling van NP is.
NP bevat alle beslissingsproblemen waarvoor een gegeven oplossing in polynomiale tijd gecontroleerd kan worden; hier behoren ook alle beslissingsproblemen uit P toe want men kan simpelweg de voorgestelde oplossing negeren en het probleem oplossen in polynomiale tijd.
NP-volledigheid
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/ee/1rightarrow_blue.svg/15px-1rightarrow_blue.svg.png)
Alle NP-volledige problemen behoren, per definitie, tot NP: een beslissingsprobleem is NP-volledig als het tot de complexiteitsklasse NP behoort en als elk ander beslissingsprobleem uit NP ernaar gereduceerd kan worden. Enkele voorbeelden van NP-volledige problemen zijn het handelsreizigersprobleem, het knapzakprobleem en het vervulbaarheidsprobleem. Het laatstgenoemde probleem was het eerste probleem waarvoor NP-volledigheid werd aangetoond.
Externe link
- (en) NP, Complexity Zoo
- ↑ (en) Descriptive Complexity