Het P-NP-probleem is een van de meest uitdagende problemen in de wiskunde en vraagt ​​zich af of er een snelle manier is om het juiste antwoord op een bepaald probleem te vinden. Als dit wordt opgelost, kan het een revolutie teweegbrengen in de manier waarop we optimalisatieproblemen oplossen in uiteenlopende sectoren, zoals vliegtuigplanning en halfgeleiderontwerp.

Een dief komt een juwelierszaak binnen, kijkt rond en denkt even na. “Ik zou graag alle sieraden meenemen, maar helaas is er een limiet aan het gewicht dat mijn tas kan dragen. Met welke edelstenen moet ik de tas vullen om het meeste geld te krijgen? Er zitten te veel mogelijke combinaties van edelstenen in de tas om hun waarde te berekenen. Als het te tijdrovend is om handmatig te berekenen, kunt u overwegen 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 dit duizenden jaren of langer duren. De reden dat dit probleem, het ‘knapzakprobleem’ genoemd, zo moeilijk is, is dat het vergelijkbaar is met het P-NP-probleem, een wiskundige uitdaging waarvan slechts 53% van de wiskundigen denkt dat deze vóór 2100 zal zijn opgelost.
Het P-NP-probleem is een van de zeven grootste wiskundige uitdagingen ter wereld. Het Clay Mathematics Institute in de VS heeft zeven onopgeloste wiskundeproblemen voor de 21e eeuw op een rij gezet en voor elk probleem een ​​premie van 1 miljoen dollar uitgeloofd. Alleen het vermoeden van Poincaré is bewezen, maar de andere zes, inclusief het P-NP-probleem, blijven onopgelost en worden door veel wiskundigen uitgedaagd. Veel optimalisatieproblemen op verschillende gebieden van de samenleving, waaronder het voorbeeld van de dief, zijn 'harde problemen' met een hoge rekencomplexiteit. Het P-NP-probleem is bedoeld om te bewijzen of er een gemakkelijke manier is om deze ‘harde 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 één bal eruit haalt en deze terugplaatst terwijl deze een groter nummer heeft dan degene die je vasthoudt, is het aantal dat je uiteindelijk krijgt het maximum, wat betekent dat je in totaal 99 vergelijkingen moet maken. Ter vergelijking: voor probleem 2 moeten we controleren of er een verzameling is die optelt tot 100 voor elke combinatie die gemaakt kan worden met 100 ballen, wat betekent dat we in het ergste geval ongeveer 2 tot de 100e macht moeten doen ( * het totale aantal subsets) van berekeningen. Zelfs als we aannemen dat een supercomputer een biljoen bewerkingen per seconde uitvoert, zou dit onvoorstelbaar lang duren, ongeveer 23 biljoen jaar.
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 reeks eenvoudige problemen die in polynomiale tijd kunnen worden beantwoord, zoals probleem 1, en de NP-set is de reeks problemen die in polynomiale tijd op juistheid kunnen worden gecontroleerd. Een P-NP-probleem is het probleem om te bewijzen of de P-set en de NP-set gelijkwaardige sets zijn. Het spreekt voor zich 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 eenvoudig te voltooien oplossing heeft, dat wil zeggen 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 op verschillende gebieden, zoals wiskunde, informatica, industriële techniek, enz., 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 lang zou duren, is het alternatief het vinden van een manier om snel en efficiënt beslissingen te nemen met een relatief kleine winst. Een optie zou kunnen zijn om 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 benaderingsoplossing die de hebzuchtige heuristiek wordt genoemd en die in de praktijk is toegepast wanneer er snel beslissingen moeten worden genomen. Hoewel deze benaderingen niet optimaal zijn, zijn ze zeer nuttig bij het nemen van beslissingen bij echte problemen met tijdsdruk. Bovendien worden sommige benaderende oplossingen steeds geavanceerder, waarbij sommige benaderingen de optimale waarde voor een bepaald probleem kunnen benaderen tot op een foutmarge van 0.5%.

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.
Het bewijzen van P=NP betekent echter niet dat alle NP-problemen gemakkelijk oplosbaar zijn. Het is echter duidelijk dat het bestaan ​​van een polynoomtijdalgoritme veel onderzoekers ertoe zal aanzetten polynomiale tijdalgoritmen voor harde NP-problemen te bestuderen. Dit zal een aanzienlijke impact hebben op efficiëntieverbeteringen en optimalisatie van problemen in de echte wereld. Omgekeerd, als blijkt dat P≠NP, betekent dit dat een dergelijke methode niet bestaat, wat betekent dat veel NP-problemen in de echte wereld hardnekkig zullen blijven. Hoe dan ook, het zal interessant zijn om te zien wat de uitkomst van dit raadsel zal zijn.