NP-compleet
| Principes |
| Complexiteitstheorie |
| Modellen |
| Algoritme |
| Turingmachine |
| Lambdacalculus |
| Theorieën |
| Berekenbaarheid |
| Complexiteitsgraad |
| NP-compleet |
NP-compleetheid is een concept uit de complexiteitstheorie. Het is een beschrijving van het inzicht uit de jaren 1970 dat er een bepaald verband is tussen de complexiteit van een groot aantal problemen die in de wiskunde en informatica als "moeilijk" worden beschouwd.
In formele zin is een probleem NP-compleet dan en slechts dan als
- het probleem tot de verzameling NP behoort.
- elk ander probleem in NP ernaar kan worden gereduceerd.
Inhoud |
[bewerk] De basis
De complexiteitstheorie is de tak van de wiskunde en de informatica die bestudeert of problemen oplosbaar zijn of niet en als ze wel oplosbaar zijn, hoe moeilijk ze dan zijn om op te lossen.
Het voornaamste hulpmiddel bij dit onderzoek is een conceptueel model van berekening, genaamd de Turingmachine. Dit model beschrijft op een zeer laag niveau en op zeer mechanische wijze hoe een berekening uitgevoerd wordt. Een dergelijke beschrijving bestaat feitelijk uit een opsomming van alle stappen die doorlopen moeten worden om van een probleemstelling tot een oplossing te komen.
Door gebruik te maken van dit model om berekeningen te beschrijven, wordt het mogelijk om te bepalen of een gegeven probleem überhaupt wel oplosbaar is. Een probleem wordt beschouwd als oplosbaar wanneer er een Turingmachine kan bestaan die het probleem beslist.
Wanneer van een probleem vaststaat dat het oplosbaar is, dient zich de vraag aan hoe moeilijk het probleem is om op te lossen. Om hier een antwoord op te geven, wordt gekeken naar de complexiteitsgraad van het probleem -- het aantal stappen dat doorlopen moet worden om het probleem op te lossen.
[bewerk] Klassen van oplosbaarheid
De verzameling van Turing-beslisbare (dat wil zeggen, de oplosbare) problemen bevat twee klassen: de klasse P van "makkelijke" op te lossen problemen en de klasse NP van "makkelijk" te verifieren problemen. Het is een open vraag of de klassen samenvallen of niet.
[bewerk] De klasse P
Over het algemeen worden die (oplosbare) problemen als "makkelijk" beschouwd, die een polynomiale complexiteit hebben. Dat wil zeggen:
In de bovenstaande term is x gerelateerd aan de grootte van de invoer voor Turingmachine A.
[bewerk] De klasse NP
Het wordt vaak gedacht dat NP voor 'niet-polynomiaal' staat, en dat de klasse NP dus uit de problemen bestaat die niet in polynomiale tijd op te lossen zijn. Dit is incorrect. NP staat voor 'niet-deterministisch polynomiaal'.
Het is bekend dat de klasse P een subset is van de klasse NP. P-problemen zijn die problemen in NP die oplosbaar zijn in polynomiale tijd.
Er zijn ook problemen in NP waarvan veel hedendaagse wiskundigen geloven dat ze niet in polynomiale tijd oplosbaar zijn (en dus "moeilijk" zijn). Voorbeelden daarvan zijn de NP-compleet problemen.
De problemen in NP worden allemaal gekarakteriseerd door een aparte eigenschap: ze zijn polynomiaal verifieerbaar. Dat wil zeggen dat we deze problemen misschien niet polynomiaal op kunnen lossen, maar als we voor een probleem een oplossing hebben dan kunnen we wel in polynomiale tijd nagaan dat die oplossing klopt. Een formele karakterisering van NP is dus:
Het is overigens acceptabel dat X een nondeterministisch algoritme is. NP is een afkorting van non-deterministisch polynomiaal verifieerbaar.
Uit de bovenstaande definitie volgt overigens dat 
. De bijzonder interessante vraag is nu: 
.
[bewerk] Reductie en NP-compleetheid
[bewerk] Reductie
In de complexiteitstheorie bestond al langer het besef dat je eigenschappen van bekende problemen over kon hevelen naar nieuwe problemen als je aan kon tonen dat je het nieuwe probleem uit kon drukken in termen van het oude probleem; dit heet het reduceren van een probleem. Een typisch voorbeeld hiervan is het probleem van het vinden van een Euler-pad, dat uitgedrukt kan worden in termen van het vinden van een Euler-cykel. Of het vinden van een Hamilton-cykel door middel van het handelsreizigersprobleem.
Aan het begin van de jaren 1970 kwamen twee zeer slimme wiskundigen -- Stephen Cook en Leonid Levin -- tot een bijzonder inzicht. Binnen de klasse NP bestaat een stelsel van problemen die aan elkaar gerelateerd zijn middels reductie in polynomiale tijd (dat wil zeggen, het omschrijven van het ene probleem in het andere kan in polynomiale tijd). Sterker nog, dit stelsel van problemen is gerelateerd aan alle problemen in NP door middel van reductie in polynomiale tijd.
Binnen NP bestaat een deelverzameling van NP. Ieder probleem in NP kan opgelost worden in termen van al deze, bijzondere problemen (het is dus ook mogelijk om deze problemen onderling tot elkaar reduceren). Cook en Levin noemden deze, bijzondere deelverzameling van NP de verzameling NPC: de verzameling van NP-complete problemen.
[bewerk] NP-compleetheid
De NP-complete problemen worden er voornamelijk door gekarakteriseerd dat ieder probleem in NP tot een NP-compleet probleem gereduceerd kan worden. Ze kunnen dus ook onderling tot elkaar gereduceerd worden. Daarmee vormen de NP-complete problemen een complete graaf van onderlinge reduceerbaarheid.
Niet alle kanten van deze graaf zijn bekend. Voor veel paren NP-complete problemen is geen manier bekend om een instantie van het ene probleem direct om te schrijven in een instantie van het andere probleem. Wel is er een boom bekend van np-complete problemen, zodat iedere instantie van ieder probleem middels een of andere omweg om te schrijven is naar ieder ander probleem. De wiskundige literatuur staat vol met uitbreidingen van deze boom (en uitbreidingen worden nog regelmatig gepubliceerd).
De introductie van NP-compleetheid in de wiskunde en informatica was een belangrijk hulpmiddel bij de classificatie van problemen. Het is echter mogelijk ook de sleutel tot de oplossing van het bovenstaande mysterie. Immers, ieder probleem in NP is reduceerbaar tot ieder NP-compleet probleem. Wordt er dus ooit een NP-compleet probleem gevonden dat polynomiaal oplosbaar is, dan volgt automatisch: P = NP.
[bewerk] Bewijs van NP-compleetheid
Om te bewijzen dat een gegeven probleem A NP-compleet is, zijn formeel twee dingen nodig:
- Een bewijs dat A behoort tot NP
- Een bewijs dat ieder probleem in NP tot A reduceert
Het eerste gedeelte is vaak eenvoudig -- het geven van een algoritme dat A verifieert in polynomiale tijd, volstaat. De uitdaging zit vaak in het tweede stuk, het bewijs dat ieder probleem in NP tot A reduceert. Problemen die aan de tweede eis voldoen worden ook wel NP-moeilijk genoemd. Het is echter ook mogelijk dat een probleem wel aan de tweede eis, maar niet aan de eerste voldoet, bijvoorbeeld de beste zet in een schaakspel kiezen, dit is ‘moeilijker’ dan NP.
Dit bewijs wordt echter meestal vereenvoudigd tot een bewijs dat een of ander probleem in NPC tot A reduceert. Dit is een uitbreiding van de "NPC-boom" en dat volstaat als bewijs. Stel namelijk dat B een probleem in NPC is. Dan reduceert ieder probleem in NP (inclusief A) tot B. Als B ook tot A reduceert, dan reduceert ieder probleem in NP tot A en wel via B.
Het begin van de "NPC-boom" wordt gevormd door het probleem SAT (satisfiability). Cook en Levin toonden de NP-compleetheid van dit probleem aan met een uitzonderlijk bewijs (waarin zij uiteraard niet het gemak hadden van het reduceren van een ander NP-compleet probleem, want hun probleem was het eerste waarvan de NP-compleetheid bekend was).
| Bron(nen): |
|
