NP (complexiteitsklasse)

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Overzicht van P, NP en NP-volledig, mits P ongelijk is aan NP.

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[bewerken]

NP kan gedefinieerd worden in termen van NTIME:

\cup_{k=1}^{\infty} \text{NTIME}(n^k).

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[bewerken]

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[bewerken]

1rightarrow blue.svg Zie NP-volledig voor het hoofdartikel over dit onderwerp.

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 links[bewerken]

Bronnen, noten en/of referenties