controleren is gemakkelijker dan vinden?
het vinden van een oplossing voor een probleem zou moeilijker moeten zijn dan het controleren of een oplossing correct is. Dat lijkt duidelijk als je ooit een sudoku puzzel hebt opgelost, of een Rubik ‘ s kubus hebt opgelost, of een spelletje schaak hebt gespeeld. Maar die uitspraak, hoe intuïtief ook, leidt ons direct naar een van de diepste wiskundige vragen die onze beschaving stelt.
non-deterministic polynomial time (of NP) problemen zijn problemen waarbij u eenvoudig kunt controleren of een antwoord correct is., In tegenstelling, zijn polynomiale tijd (of P) problemen die
waar het vinden van het antwoord gemakkelijk is. Als je het antwoord kunt vinden, dan heb je het gecontroleerd om correct te zijn, dus elk probleem in P is ook in NP. We zeggen dat P een subklasse van NP is. We weten echter niet of er een specifiek probleem is in NP dat niet in P staat, en dat is wat we het P vs NP probleem noemen.
Het P vs NP-probleem is een van de meest centrale onopgeloste problemen in de wiskunde en de theoretische informatica. Er is zelfs een Clay Millennium prijs die een miljoen dollar biedt voor zijn oplossing., Er zijn echter waarschijnlijk veel eenvoudiger manieren om miljonair te worden dan het oplossen van P vs NP!
Er was onlangs een buzz toen iemand beweerde het op arXiv op te lossen, hoewel er snel een gat in het bewijs werd gevonden. Gezien de recente interesse in het probleem en de centrale plaats ervan in de wiskunde, bespreek ik het in de blog van deze week.
Sudoku
Als u een ingevulde Sudoku-puzzel in een krant krijgt, kunt u deze in de prullenbak gooien. Maar als je wilt, kun je door de rijen, kolommen en 3 x 3 cellen scannen om te zien dat het een geldige oplossing is: elk van 1, 2, … , 9 moet precies één keer voorkomen., Dat is analoog aan NP, omdat het relatief eenvoudig is om te controleren of een oplossing correct is.
echter, als ik je een gedeeltelijk gevulde Sudoku puzzel geef, kan het moeilijk zijn om de oplossing te vinden. Dat is de vreugde en uitdaging van dit soort puzzel. Dus in NP zijn lijkt niet meteen te impliceren dat het probleem een gemakkelijk te vinden oplossing heeft. Die intuïtie is de kern van het P vs NP probleem.
precieze formulering
om P en NP nauwkeuriger te begrijpen, moeten we algoritmen beter begrijpen en hun snelheid meten. Problemen worden gesteld met een aantal vaste input en output Ja of nee. De input is een gegeven lengte, zeg n, waarbij n een positief geheel getal is. Dit is het aantal bits dat nodig is om de invoer uit te drukken. Een algoritme is een methode of procedure voor het oplossen van een probleem. Algoritmen geven instructies bij elke stap in een berekening en moeten beëindigen., De stappen kunnen seconden, milliseconden, of een andere vaste interval van de tijd die afhankelijk is van uw probleem.
de complexiteit van een probleem is de minimale worst-case looptijd van alle mogelijke algoritmen die het probleem oplossen als functie van de lengte van de invoer. Met andere woorden, het meet hoe lang het duurt om het probleem op te lossen met het snelste algoritme, maar met de worst case input.
een probleem is oplosbaar in polynomiale tijd indien gegeven een input van lengte n, de complexiteit wordt hierboven begrensd door de polynomiale functie nm voor een niet-negatief geheel getal m., De verzameling van alle problemen oplosbaar in polynoom tijd wordt aangeduid door P.
in P betekent niet noodzakelijkerwijs dat het probleem haalbaar is. Bijvoorbeeld, als het N1000 stappen neemt om het algoritme uit te voeren, dan zal het hopeloos traag zijn, zelfs voor kleine n. niet-deterministische polynoom (of NP) problemen zijn degenen waar u kunt controleren of het ja-antwoord correct is in polynoom tijd.
NP-hardheid
een probleem is NP-hard als een polynoom-tijdalgoritme daarvoor een polynoom-tijdalgoritme zou impliceren voor elk probleem in NP. Dus, als een NP-hard probleem in P was, dan P = NP., De NP-harde problemen zijn minstens zo moeilijk als elk probleem in NP. Een NP-compleet probleem is er een die NP-hard is en in NP.
een klassiek NP-compleet probleem is het vinden van een Hamilton-cyclus. Stel dat we hiervoor een netwerk van steden hebben die verbonden zijn door wegen. Het probleem is om elke stad te bezoeken via de wegen (geen vliegtuigen toegestaan!) en kom terug naar het begin. Dit lijkt gemakkelijk voor een klein aantal steden, maar als je er honderden kreeg dan wordt het moeilijk., Duizenden andere NP-complete problemen zijn bekend die zich voordoen in de grafentheorie, getaltheorie, meetkunde en andere gebieden van de wiskunde en informatica.
Wat is het antwoord?
als Ik zou wedden, dan zou ik aannemen dat P niet gelijk is aan NP, en ik denk dat de meeste experts het eens zouden zijn. We zouden vreselijk dom moeten zijn om niet te zien hoe alle duizenden NP-complete problemen geen polynoom-tijdalgoritme hebben. Maar als soort is dom onze standaardpositie, zodat niemand met 100% zekerheid kan zeggen wat het antwoord is.,
wat interessant is aan het P vs NP probleem is dat het wijst op hoe beperkt ons begrip is in het bewijzen dat bepaalde problemen geen snelle oplossingen hebben. Dit is onderdeel van een groter thema op het gebied van computationele complexiteitstheorie, dat tientallen andere complexiteitsklassen bestudeert. Bekijk de complexity zoo voor een lijst van deze klassen. Voor het grootste deel, het is open om te laten zien verschillende (vaak exotisch klinkende) complexiteit klassen zijn de juiste subklassen van elkaar. Het is bijvoorbeeld onbekend of NL een juiste subklasse van P is, en we weten niet of FPT een juiste subklasse van W.,
ongeacht de waarheidsgetrouwheid, zal het P vs NP-probleem waarschijnlijk nog enige tijd open blijven. Tenzij bewezen is dat P = NP, Sudoku veilig blijft.
Anthony Bonato