P-NP-problemet er en udfordring i matematik og datalogi, men kan det være nøglen til at løse komplekse problemer i den virkelige verden?

Rygsækproblemet og P-NP-gåden

En tyv går ind i en smykkebutik, ser sig omkring og tænker kort. “Så meget som jeg gerne vil tage alle smykkerne med, er der en grænse for, hvor meget vægt min taske kan holde. Hvilke ædelstene skal jeg fylde posen med for at få flest penge?” Der er for mange mulige kombinationer af ædelstene i posen til at beregne deres værdi. Hvis det er for tidskrævende at beregne i hånden, kan du overveje at bruge de mest avancerede computere og software med de bedste algoritmer. Desværre findes der i øjeblikket ingen algoritme til at løse dette problem hurtigt. Selv med de mest kraftfulde computere ville det tage tusinder af år eller mere. Grunden til, at dette problem, kaldet "knapsækkeproblemet", er så vanskeligt, er, at det ligner P-NP-problemet, som kun 53% af matematikerne tror vil blive løst før 2100.
P-NP-problemet er en af ​​verdens syv største matematikudfordringer. Clay Institute of Mathematics i USA har listet syv uløste matematikproblemer for det 21. århundrede og tilbudt en dusør på 1 million dollars for hver enkelt. Kun Poincaré-formodningen er blevet bevist, men de andre seks, inklusive P-NP-problemet, forbliver uløste og udfordret af mange matematikere. Mange optimeringsproblemer på forskellige områder af samfundet, herunder tyvens eksempel, er "hårde problemer" med høj beregningsmæssig kompleksitet. P-NP-problemet er at bevise, om der er en nem måde at løse disse "hårde problemer".

Hvad er beregningsmæssig kompleksitet?

Beregningsmæssig kompleksitet er et objektivt mål for, hvor svært det problem, vi forsøger at løse, er. I denne sammenhæng betyder hårdhed ikke, at der ikke er nogen løsning på problemet, men snarere at der ikke er en algoritme, der kan løse problemet hurtigt.
Her er et nemt eksempel. Der er 100 kugler med forskellige tilfældige tal skrevet på dem.

– Opgave 1: Hvad er den maksimale værdi af tallene skrevet på kuglerne?
– Opgave 2: Er der et sæt kugler, således at summen af ​​tallene skrevet på kuglerne er 100?

For opgave 1, hvis du tager en kugle ud og erstatter den, når den har et større tal end den, du holder, er det antal, du ender med, maksimum, hvilket betyder, at du skal lave 99 sammenligninger i alt. Til sammenligning skal vi for opgave 2 kontrollere, om der er et sæt, der summerer til 100 for hver kombination, der kan laves med 100 bolde, hvilket betyder, at vi i værste fald skal gøre omkring 2 til 100. potens (* det samlede antal delmængder) af beregninger. Det er ufattelig lang tid, omkring 23 kvadrillioner år, selvom vi antager, at en supercomputer udfører kvadrillion operationer i sekundet.
En algoritme kaldes en polynomiel tidsalgoritme, hvis antallet af operationer (N-1) efterhånden som antallet af kugler (N) stiger, ikke overstiger en polynomiel funktion af antallet af kugler, som i løsningen til opgave 1. eksistensen af ​​en sådan algoritme kan være forskellen mellem et let problem og et svært problem.

P=NP?

Bemærk, at det kræver en enorm mængde beregning at finde svaret på det svære problem 2, for hvilket der ikke findes en polynomiel tidsalgoritme, men at verificere, at svaret er korrekt, er meget simpelt. Givet et sæt kugler bør det tage mindre end 10 sekunder at bekræfte, at summen af ​​de nedskrevne tal er 100. Med andre ord, bare fordi et problem er let at beregne, betyder det ikke, at der er en nem måde at løse det på. . Om der er en nem måde at løse det på, og matematikere ikke har fundet det endnu, eller om der ikke er nogen nem måde at løse det på i første omgang, skal vise sig. Dette er P-NP-problemet.
P-sættet er det sæt af lette problemer, der kan besvares i polynomisk tid, såsom opgave 1, og NP-sættet er det sæt af problemer, der kan kontrolleres for rigtighed i polynomiets tid. Et P-NP-problem er problemet med at bevise, om P-sættet og NP-sættet er ækvivalente mængder. Det er indlysende, at P-sættet hører til NP-sættet. Det er dog endnu ikke blevet bevist, at ethvert problem i NP-sættet er i P-sættet. Hvis dette er bevist, betyder det, at ethvert problem, der er let at beregne, har en let-at-fuldstændig løsning, dvs. vi behøver ikke længere 10^28 år til at løse opgave 2.

NP-problemer og det virkelige liv

Det er ikke kun den matematiske sværhedsgrad ved P-NP-problemet, der gør det til et af de syv bedste matematiske problemer nogensinde. Grunden til, at det er så vigtigt at bevise, er, at det er tæt forbundet med at løse problemer i den virkelige verden. Problemer i den virkelige verden i industrier så forskellige som planlægning af fly, halvlederdesign, placering af boremaskiner, genomisk dataanalyse, placering af astronomiske teleskoper og røntgenkrystallografi er NP-hårde problemer, som tager lang tid at løse. Vi mangler dog endnu at finde en algoritme til at træffe optimale beslutninger hurtigt, og vi ved ikke engang, om en sådan algoritme findes. Så i mangel af en polynomial-tidsalgoritme, hvordan træffer vi i øjeblikket beslutninger om problemer i den virkelige verden?
Forskere inden for forskellige områder såsom matematik, datalogi, industriteknik osv. forsker i og udvikler forskellige omtrentlige løsninger, der tilnærmer den optimale løsning til at løse problemer i den virkelige verden. Overvej igen tyvens problem: Hvis det ville tage lang tid at finde den optimale kombination af ædelstene, er alternativet at finde en måde at træffe beslutninger hurtigt og effektivt med et relativt lille overskud. En måde at gøre dette på kan være at beregne værdien pr. vægt af hver ædelsten og fylde din taske med ædelstene med den højeste værdi pr. vægt først. Dette er en tilnærmet løsning kaldet den grådige heuristik, som er blevet brugt i praksis, når beslutninger skal træffes hurtigt. Selvom disse tilnærmelser ikke er optimale, er de meget nyttige til at træffe beslutninger i virkelige problemer med tidsbegrænsninger. Ydermere bliver nogle tilnærmede løsninger mere sofistikerede, idet nogle tilnærmelser er i stand til at tilnærme den optimale værdi for et givet problem til inden for 0.5 % fejl.

Sikkerhedsindustrien og NP-problemer

I modsætning til ovennævnte industrier er der én industri, der ikke ønsker, at der skal findes en nem algoritme til at løse NP-problemer. Dette er sikkerhedsindustrien. Nuværende sikkerhedsordninger er organiseret på en måde, der bruger NP-problemet omvendt. Hvis du kender et kodeord, er det nemt at verificere, at det er det rigtige kodeord, men det er ikke nemt at finde det, fordi der ikke er nogen polynomisk tidsalgoritme til at finde det. Måske håber hele sikkerhedsindustrien, at P-NP-problemet forbliver en evig gåde.
Selvom P=NP er bevist, betyder det ikke, at alle NP-problemer er lette at løse. Det er dog klart, at eksistensen af ​​en polynomial-tidsalgoritme vil anspore mange forskere til at studere polynomial-tidsalgoritmer for hårde NP-problemer. Dette vil have en betydelig indvirkning på effektivitetsforbedringer og optimering af problemer i den virkelige verden. Omvendt, hvis det viser sig, at P≠NP, betyder det, at der ikke er en sådan metode, hvilket betyder, at mange NP-problemer vil forblive uløselige i den virkelige verden. Uanset hvad, vil det være interessant at se, hvad resultatet af denne gåde bliver.