NP (complexiteitsklasse)

In dit artikel zullen we onderzoeken welke impact NP (complexiteitsklasse) heeft gehad op de moderne samenleving. Sinds zijn opkomst heeft NP (complexiteitsklasse) de aandacht en interesse getrokken van mensen van alle leeftijden en achtergronden, en is het een onderwerp van discussie geworden in verschillende sociale kringen. Door de jaren heen heeft NP (complexiteitsklasse) zich ontwikkeld en aangepast aan culturele en technologische veranderingen, waardoor het relevant blijft in een voortdurend veranderende wereld. In deze verkenning zullen we bekijken hoe NP (complexiteitsklasse) ons leven heeft beïnvloed, van de implicaties ervan in de politiek en economie tot de impact ervan op de populaire cultuur en entertainment.

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.

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

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 er in polynomiale tijd naar 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.

  • (en) NP, Complexity Zoo