title: NP (complexiteitsklasse)
text: 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.
  
  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 
  
  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 
    NP, Complexity Zoo
  
  Complexiteitsklasse