NP is de klasse van talen die polynomiale tijdverificateurs hebben
De klasse NP, wat staat voor 'niet-deterministische polynomiale tijd', is een fundamenteel concept in de computationele complexiteitstheorie, een deelgebied van de theoretische informatica. Om NP te begrijpen, moet je eerst het begrip beslissingsproblemen begrijpen, dit zijn vragen met een ja-of-nee-antwoord. Een taal verwijst in deze context naar een reeks strings over een bepaald alfabet, waarbij elke string een exemplaar van een beslissingsprobleem codeert.
Er wordt gezegd dat een taal (L) in NP is als er een polynomiale tijdverificatie voor (L) bestaat. Een verifier is een deterministisch algoritme (V) dat twee invoer nodig heeft: een instantie (x) en een certificaat (y). Het certificaat (y) wordt ook wel 'getuige' of 'bewijs' genoemd. De verificateur (V) controleert of het certificaat (y) bevestigt dat (x) tot de taal (L) behoort. Formeel is een taal (L) in NP als er een polynoom-tijdalgoritme (V) en een polynoom (p(n)) bestaat, zodat er voor elke string (x in L) een string (y) bestaat met ( |y| leq p(|x|)) en (V(x, y) = 1). Omgekeerd is er voor elke string (x notin L) geen string (y) zodanig dat (V(x, y) = 1).
Om dit concept te verduidelijken, kunnen we het bekende probleem van de ‘Boolean satisfiability’ (SAT) overwegen. Het SAT-probleem vraagt zich af of er een toewijzing van waarheidswaarden aan variabelen in een bepaalde Booleaanse formule bestaat, zodat de formule uitkomt op waar. Het SAT-probleem ligt in NP omdat, gegeven een Booleaanse formule ( phi ) en een toewijzing ( alpha ) van waarheidswaarden aan zijn variabelen, men in polynomiale tijd kan verifiëren of ( alpha ) voldoet aan ( phi ). Hier is de instantie ( x ) de Booleaanse formule ( phi ) en het certificaat ( y ) de toewijzing ( alpha ). De verificateur (V) controleert of (alfa) (phi) waar maakt, wat kan worden gedaan in polynomiale tijd met betrekking tot de grootte van (phi).
Een ander illustratief voorbeeld is het ‘Hamiltonian Path’-probleem. Dit probleem vraagt zich af of er een pad bestaat in een bepaalde grafiek dat elk hoekpunt precies één keer bezoekt. Het Hamiltoniaanse padprobleem komt ook voor in NP omdat, gegeven een grafiek (G) en een reeks hoekpunten (P), men in polynomiale tijd kan verifiëren of (P) een Hamiltoniaans pad is in (G). In dit geval is de instantie ( x ) de grafiek ( G ) en het certificaat ( y ) de reeks hoekpunten ( P ). De verificateur (V) controleert of (P) een Hamiltoniaans pad vormt, wat in polynomiale tijd kan worden gedaan met betrekking tot de grootte van (G).
Het concept van verifieerbaarheid in polynomiale tijd is belangrijk omdat het een manier biedt om problemen te karakteriseren die efficiënt controleerbaar zijn, zelfs als het vinden van de oplossing rekenkundig onhaalbaar zou kunnen zijn. Dit leidt tot de beroemde vraag of ( P = NP ), die vraagt of elk probleem waarvan de oplossing in polynomiale tijd kan worden geverifieerd, ook in polynomiale tijd kan worden opgelost. De klasse ( P ) bestaat uit beslissingsproblemen die in polynomiale tijd kunnen worden opgelost door een deterministische Turingmachine. Als ( P = NP ), zou dit betekenen dat elk probleem met een verificator in polynomiale tijd ook een oplosser in polynomiale tijd heeft. Deze vraag blijft een van de belangrijkste open problemen in de computerwetenschap.
Een van de belangrijkste eigenschappen van NP is dat het gesloten is onder polynomiale tijdsreducties. Een polynomiale tijdreductie van een taal (L_1) naar een taal (L_2) is een polynomiale tijdberekenbare functie (f) zodanig dat ( x in L_1 ) dan en slechts dan als (f(x) in L_2 ). Als er een polynomiale tijdsreductie bestaat van (L_1) naar (L_2) en (L_2) in NP is, dan is (L_1) ook in NP. Deze eigenschap speelt een belangrijke rol bij de studie van NP-volledigheid, die de "moeilijkste" problemen in NP identificeert. Een probleem is NP-compleet als het zich in NP bevindt en elk probleem in NP er in polynomiale tijd toe kan worden herleid. Het SAT-probleem was het eerste probleem waarvan bewezen werd dat het NP-compleet is, en het dient als basis voor het bewijzen van de NP-volledigheid van andere problemen.
Om het concept van verifieerbaarheid in polynomiale tijd verder te illustreren, kunt u het probleem "Subset Sum" overwegen. Dit probleem vraagt zich af of er een subset bestaat van een gegeven set gehele getallen die opgeteld een gespecificeerde doelwaarde oplevert. Het Subset Sum-probleem doet zich voor in NP omdat, gegeven een reeks gehele getallen ( S ), een doelwaarde ( t ) en een subset ( S ' ) van ( S ), men in polynomiale tijd kan verifiëren of de som van de elementen in (S') is gelijk aan (t). Hier is de instantie ( x ) het paar ( (S, t) ), en het certificaat ( y ) is de subset ( S' ). De verificateur (V) controleert of de som van de elementen in (S') gelijk is aan (t), wat kan worden gedaan in polynomiale tijd met betrekking tot de grootte van (S).
Het belang van polynomiale-tijd verifieerbaarheid reikt verder dan theoretische overwegingen. In praktische zin betekent het dat voor problemen in NP, als een voorgestelde oplossing (certificaat) wordt verstrekt, deze efficiënt kan worden gecontroleerd. Dit heeft belangrijke implicaties voor cryptografische protocollen, optimalisatieproblemen en verschillende gebieden waar het verifiëren van de correctheid van een oplossing belangrijk is.
Samenvattend omvat de klasse NP beslissingsproblemen waarvoor een voorgestelde oplossing in polynomiale tijd kan worden geverifieerd door een deterministisch algoritme. Dit concept is fundamenteel in de computationele complexiteitstheorie en heeft diepgaande implicaties voor zowel theoretische als praktische aspecten van de informatica. De studie van NP, verifieerbaarheid in polynomiale tijd en aanverwante concepten zoals NP-volledigheid blijft een levendig en kritisch onderzoeksgebied.
Andere recente vragen en antwoorden over Ingewikkeldheid:
- Is de PSPACE-klasse niet gelijk aan de EXPSPACE-klasse?
- Is de P-complexiteitsklasse een subset van de PSPACE-klasse?
- Kunnen we bewijzen dat de Np- en P-klasse hetzelfde zijn door een efficiënte polynomiale oplossing te vinden voor elk NP-volledig probleem op een deterministische TM?
- Kan de NP-klasse gelijk zijn aan de EXPTIME-klasse?
- Zijn er problemen in PSPACE waarvoor geen NP-algoritme bekend is?
- Kan een SAT-probleem een NP-volledig probleem zijn?
- Kan een probleem zich in de NP-complexiteitsklasse bevinden als er een niet-deterministische turingmachine is die het in polynomiale tijd oplost?
- Zijn P en NP eigenlijk dezelfde complexiteitsklasse?
- Is elke contextvrije taal in de P-complexiteitsklasse?
- Is er een tegenstrijdigheid tussen de definitie van NP als een klasse van beslissingsproblemen met polynomiale tijdverificateurs en het feit dat problemen in de klasse P ook polynomiale tijdverificateurs hebben?
Bekijk meer vragen en antwoorden in Complexiteit