Het P-NP-probleem is een uitdaging in de wiskunde en computerwetenschappen, maar kan het de sleutel zijn tot het oplossen van complexe problemen in de echte wereld?
Het rugzakprobleem en het P-NP-raadsel
Een dief komt een juwelierszaak binnen, kijkt rond en denkt even na. "Hoe graag ik ook al mijn sieraden mee zou willen nemen, er is een limiet aan hoeveel gewicht mijn tas kan dragen. Met welke edelstenen moet ik de tas vullen om het meeste geld te krijgen?" Er zijn te veel mogelijke combinaties van edelstenen in de tas om hun waarde te berekenen. Als het te tijdrovend is om het met de hand te berekenen, kun je overwegen om de meest geavanceerde computers en software met de beste algoritmen te gebruiken. Helaas bestaat er momenteel geen algoritme om dit probleem snel op te lossen. Zelfs met de krachtigste computers zou het duizenden jaren of langer duren. De reden dat dit probleem, het "knapsackprobleem" genoemd, zo moeilijk is, is dat het lijkt op het P-NP-probleem, waarvan slechts 53% van de wiskundigen gelooft dat het voor 2100 zal zijn opgelost.
Het P-NP-probleem is een van de zeven grootste wiskundige uitdagingen ter wereld. Het Clay Institute of Mathematics in de VS heeft zeven onopgeloste wiskundige problemen voor de 21e eeuw op een rijtje gezet en voor elk probleem een beloning van 1 miljoen dollar uitgeloofd. Alleen de Poincaré-hypothese is bewezen, maar de andere zes, waaronder het P-NP-probleem, zijn nog steeds onopgelost en worden door veel wiskundigen uitgedaagd. Veel optimalisatieproblemen in verschillende maatschappelijke gebieden, waaronder het voorbeeld van de dief, zijn "moeilijke problemen" met een hoge computationele complexiteit. Het P-NP-probleem moet bewijzen of er een gemakkelijke manier is om deze "moeilijke problemen" op te lossen.
Wat is computationele complexiteit?
Computationele complexiteit is een objectieve maatstaf voor hoe moeilijk het probleem dat we proberen op te lossen is. In deze context betekent hardheid niet dat er geen oplossing voor het probleem is, maar eerder dat er geen algoritme is dat het probleem snel kan oplossen.
Hier is een eenvoudig voorbeeld. Er zijn 100 ballen met verschillende willekeurige getallen erop geschreven.
– Probleem 1: Wat is de maximale waarde van de getallen die op de ballen staan?
– Probleem 2: Bestaat er een set ballen waarbij de som van de op de ballen geschreven getallen 100 is?
Voor Probleem 1, als je een bal eruit haalt en vervangt wanneer deze een groter getal heeft dan het getal dat je vasthoudt, is het getal dat je overhoudt het maximum, wat betekent dat je in totaal 99 vergelijkingen moet maken. Ter vergelijking, voor Probleem 2, moeten we controleren of er een set is die optelt tot 100 voor elke combinatie die kan worden gemaakt met 100 ballen, wat betekent dat we in het ergste geval ongeveer 2 tot de 100e macht (* het totale aantal subsets) aan berekeningen moeten doen. Dit is een onvoorstelbaar lange tijd, ongeveer 23 quadriljoen jaar, zelfs als we aannemen dat een supercomputer een quadriljoen bewerkingen per seconde uitvoert.
Een algoritme wordt een polynoomtijdalgoritme genoemd als, naarmate het aantal ballen (N) toeneemt, het aantal bewerkingen (N-1) een polynomiale functie van het aantal ballen niet overschrijdt, zoals in de oplossing van probleem 1. Het bestaan van een dergelijk algoritme kan het verschil betekenen tussen een eenvoudig probleem en een moeilijk probleem.
P=NP?
Merk op dat het vinden van het antwoord op het moeilijke probleem 2, waarvoor geen polynomiaal tijdalgoritme bestaat, een enorme hoeveelheid berekeningen vereist, maar het verifiëren dat het antwoord juist is heel eenvoudig is. Gegeven een set ballen zou het minder dan 10 seconden moeten duren om te verifiëren dat de som van de opgeschreven getallen 100 is. Met andere woorden: het feit dat een probleem gemakkelijk te berekenen is, betekent niet dat er een gemakkelijke manier is om het op te lossen. . Of er een gemakkelijke manier is om het op te lossen en dat wiskundigen het nog niet hebben gevonden, of dat er überhaupt geen gemakkelijke manier is om het op te lossen, valt nog te bezien. Dit is het P-NP-probleem.
De P-set is de set van eenvoudige problemen die in polynomiale tijd kunnen worden beantwoord, zoals Probleem 1, en de NP-set is de set van problemen die op correctheid kunnen worden gecontroleerd in polynomiale tijd. Een P-NP-probleem is het probleem om te bewijzen of de P-set en de NP-set equivalente sets zijn. Het is vanzelfsprekend dat de P-set tot de NP-set behoort. Het is echter nog niet bewezen dat elk probleem in de NP-set zich in de P-set bevindt. Als dit wordt bewezen, betekent dit dat elk probleem dat gemakkelijk te berekenen is, een gemakkelijk te voltooien oplossing heeft, d.w.z. dat we niet langer 10^28 jaar nodig hebben om Probleem 2 op te lossen.
NP-problemen en het echte leven
Het is niet alleen de wiskundige moeilijkheid van het P-NP-probleem die het tot een van de zeven grootste wiskundige problemen aller tijden maakt. De reden dat het zo belangrijk is om te bewijzen, is dat het nauw verband houdt met het oplossen van problemen in de echte wereld. Problemen uit de praktijk in sectoren die zo uiteenlopend zijn als vliegtuigplanning, halfgeleiderontwerp, plaatsing van boormachines, genomische data-analyse, plaatsing van astronomische telescopen en röntgenkristallografie zijn NP-moeilijke problemen die veel tijd vergen om op te lossen. We moeten echter nog een algoritme ontdekken om snel optimale beslissingen te nemen, en we weten niet eens of zo'n algoritme bestaat. Hoe nemen we, bij gebrek aan een polynomiaal tijdalgoritme, momenteel beslissingen over problemen in de echte wereld?
Geleerden in verschillende vakgebieden zoals wiskunde, computerwetenschappen, industriële techniek, etc. onderzoeken en ontwikkelen verschillende benaderende oplossingen die de optimale oplossing benaderen om echte problemen op te lossen. Denk nog eens aan het probleem van de dief: als het vinden van de optimale combinatie van edelstenen veel tijd zou kosten, is het alternatief om een manier te vinden om snel en efficiënt beslissingen te nemen met een relatief kleine winst. Een manier om dit te doen, is door de waarde per gewicht van elke edelsteen te berekenen en je tas eerst te vullen met de edelstenen met de hoogste waarde per gewicht. Dit is een benaderende oplossing die de hebzuchtige heuristiek wordt genoemd, die in de praktijk is gebruikt wanneer er snel beslissingen moeten worden genomen. Hoewel deze benaderingen niet optimaal zijn, zijn ze erg handig bij het nemen van beslissingen in echte problemen met tijdsbeperkingen. Bovendien worden sommige benaderende oplossingen steeds geavanceerder, waarbij sommige benaderingen de optimale waarde voor een bepaald probleem kunnen benaderen tot binnen 0.5% fout.
De veiligheidsindustrie en NP-problemen
In tegenstelling tot de bovengenoemde industrieën is er één industrie die niet wil dat er een eenvoudig algoritme wordt gevonden om NP-problemen op te lossen. Dit is de beveiligingsindustrie. De huidige beveiligingssystemen zijn zo georganiseerd dat het NP-probleem in omgekeerde richting wordt gebruikt. Als u een wachtwoord kent, kunt u eenvoudig verifiëren dat dit het juiste wachtwoord is, maar het is niet eenvoudig om het te vinden omdat er geen algoritme voor polynoomtijd is om het te vinden. Misschien hoopt de hele veiligheidsindustrie dat het P-NP-probleem een eeuwigdurend raadsel zal blijven.
Zelfs als P=NP bewezen is, betekent dit niet dat alle NP-problemen eenvoudig oplosbaar zijn. Het is echter duidelijk dat het bestaan van een polynomiaal-tijdalgoritme veel onderzoekers ertoe zal aanzetten om polynomiaal-tijdalgoritmen voor moeilijke NP-problemen te bestuderen. Dit zal een aanzienlijke impact hebben op efficiëntieverbeteringen en optimalisatie van echte problemen. Omgekeerd, als blijkt dat P≠NP, betekent dit dat er geen dergelijke methode is, wat betekent dat veel NP-problemen onoplosbaar zullen blijven in de echte wereld. Hoe dan ook, het zal interessant zijn om te zien wat de uitkomst van dit raadsel zal zijn.
