het oude P versus NP probleem
dus wat is dan het P versus NP probleem?
voor de goede orde, de status quo is dat P≠NP.
P (polynomiale tijd) verwijst naar de klasse van problemen die kunnen worden opgelost door een algoritme in polynomiale tijd. Problemen in de P-klasse kunnen variëren van alles zo eenvoudig als vermenigvuldigen tot het vinden van het grootste getal in een lijst. Ze zijn de relatief ‘gemakkelijker’ set van problemen.
NP (non-deterministic polynomial time) verwijst naar de klasse van problemen die in polynomiale tijd kunnen worden opgelost door een niet-deterministische computer., Dit is in wezen een andere manier om te zeggen: “als ik onbeperkte rekenkracht heb (dat wil zeggen zoveel computers als ik nodig heb), ben ik in staat om elk probleem op te lossen in de meeste polynomiale tijd”. Meer intuïtief echter, verwijst het naar de klasse van problemen die momenteel, heeft geen manier om een snelle (polynomiale tijd) genoeg antwoord te vinden, maar kan snel worden geverifieerd (in polynomiale tijd) als men de oplossing voor het probleem biedt. De term geverifieerd hier betekent dat men in staat is om te controleren of de geleverde oplossing inderdaad correct is.
duidelijk, gebaseerd op de bovenstaande definitie, P ⊆ NP., Laten we eens kijken naar een voorbeeld om dit abstracte probleem te illustreren.
een van de meest voorkomende maar effectieve voorbeelden is Sudoku. Gegeven een onopgelost Sudoku-raster (9 x 9 bijvoorbeeld), zou het een algoritme behoorlijk wat tijd kosten om er een op te lossen. Echter, als het 9 x 9 raster toeneemt tot een 100 x 100 of 10.000 x 10.000 raster, zou de tijd die nodig is om het op te lossen exponentieel toenemen omdat het probleem zelf aanzienlijk moeilijker wordt., Echter, gegeven een opgelost Sudoku-raster (van 9 x 9), is het vrij eenvoudig om te verifiëren dat de specifieke oplossing inderdaad correct is, zelfs als de grootte schaal tot 10.000 bij 10.000. Het zou langzamer zijn, maar de tijd om een oplossing te controleren neemt langzamer toe (polynomiaal).
Er zijn veel andere NP-problemen, waaronder het Knapzakprobleem en het probleem van de reizende verkopers, en ze zijn vergelijkbaar in die zin dat ze moeilijk op te lossen zijn, maar snel te verifiëren., Het fundamentele probleem dat we hier proberen op te lossen is:
betekent het snel herkennen van NP correcte antwoorden dat er ook een snelle manier is om ze te vinden?
als dat zo is (dat wil zeggen P=NP), kan dit sterk veranderen hoe we naar deze NP-problemen kijken, omdat dat betekent dat er een snelle manier is om al deze problemen op te lossen, alleen dat we nog niet hebben kunnen achterhalen hoe.
als dit niet ingewikkeld genoeg is, laten we het wat pittiger maken.,
onder deze NP-problemen bestaat er een koning van alle problemen die onderzoekers NP-Complete problemen noemen. Formeel zijn ze een reeks problemen waarbij elk ander NP-probleem in de polynomiale tijd kan worden verminderd (hieronder behandeld) en waarvan de oplossing nog steeds in de polynomiale tijd kan worden geverifieerd. Dit betekent dat elk NP-probleem kan worden omgezet in een NP-compleet probleem.
informeel zijn zij de “moeilijkste” van de NP-problemen., Dus als Om het even welk NP-volledig probleem in polynomiale tijd kan worden opgelost, dan kan elk NP-volledig probleem in polynomiale tijd worden opgelost, en elk probleem in NP kan in polynomiale tijd worden opgelost (d.w.z. P=NP). Het beroemdste voorbeeld zou het probleem van de reizende verkopers zijn.
bestaat er ook een reeks problemen genaamd NP-Hard problems., Deze problemen zijn minstens zo moeilijk als NP-problemen, maar zonder de voorwaarde dat het in polynomiale tijd moet worden opgelost. Dit suggereert dat NP-harde problemen niet noodzakelijkerwijs deel uitmaken van de NP-klasse. Een voorbeeld zou zijn het oplossen van een schaakbord — gegeven een toestand van een schaakbord, is het bijna onmogelijk om te zeggen of een bepaalde zet in de gegeven toestand, is in feite de optimale zet. Formeel bestaat er geen polynomiaal tijdalgoritme om een oplossing voor een NP-Hard probleem te verifiëren.,
als we de twee samenvoegen, betekent een NP-compleet probleem dat het NP-Hard is, maar een NP-Hard probleem betekent niet dat het NP-compleet is.
Defining NP-volledigheid
een probleem L, is NP-compleet als:
- L is NP-Hard
- L behoort tot NP
het onderstaande diagram (focus op de linkerkant) moet de dingen duidelijker maken.,
Wait, what does it mean by reducing A to B?
Reduction forms the crux of NP-Completeness.,
informeel kan een probleem L1 worden teruggebracht tot een ander probleem L2 als:
- elke instantie van L1 kan worden gemodelleerd als een instantie van L2
- de oplossing voor het laatste biedt een oplossing voor het eerste en vice versa
om dit intuïtief te begrijpen, kan men het als volgt zien:
als L1 is reduceerbaar tot L2, L1 moet maximaal zo hard zijn als L2. Omgekeerd moet L2 minstens even hard zijn als L1.
wiskundig wordt dit aangeduid als: L1 ≤p L2 (gelezen als “L1 is polynomiaal reduceerbaar tot L2”).,
