P-NP probleem on matemaatikas ja arvutiteaduses väljakutse, aga kas see võiks olla võtmeks keeruliste reaalsete probleemide lahendamisel?
Seljakoti probleem ja P-NP mõistatus
Varas siseneb juveelipoodi, vaatab ringi ja mõtiskleb lühidalt. „Kuigi ma tahaksin kõik ehted endaga kaasa võtta, on mu koti kandevõime piiratud. Milliste kalliskividega peaksin koti täitma, et kõige rohkem raha saada?“ Kotis on liiga palju võimalikke kalliskivide kombinatsioone, et nende väärtust arvutada. Kui käsitsi arvutamine on liiga aeganõudev, võite kaaluda kõige arenenumate arvutite ja tarkvara kasutamist parimate algoritmidega. Kahjuks pole praegu ühtegi algoritmi, mis seda probleemi kiiresti lahendaks. Isegi kõige võimsamate arvutitega kuluks selleks tuhandeid aastaid või rohkem. Põhjus, miks see „seljakotiprobleemiks“ nimetatud probleem on nii keeruline, on see, et see sarnaneb P-NP probleemiga, mille lahendamist enne aastat 53 usub vaid 2100% matemaatikutest.
P-NP probleem on üks maailma seitsmest suurimast matemaatikaülesandest. USA Clay Matemaatikainstituut on loetlenud seitse 21. sajandi lahendamata matemaatikaülesannet ja pakkunud igaühe eest miljoni dollari suuruse pearaha. Ainult Poincaré hüpotees on tõestatud, kuid ülejäänud kuus, sealhulgas P-NP probleem, on endiselt lahendamata ja paljud matemaatikud on neid vaidlustanud. Paljud optimeerimisülesanded ühiskonna erinevates valdkondades, sealhulgas varga näide, on "rasked probleemid", millel on suur arvutuslik keerukus. P-NP probleemi eesmärk on tõestada, kas nende "raskete probleemide" lahendamiseks on olemas lihtne viis.
Mis on arvutuslik keerukus?
Arvutuslik keerukus on objektiivne mõõt selle kohta, kui keeruline on probleem, mida me püüame lahendada. Selles kontekstis ei tähenda keerukus seda, et probleemile pole lahendust, vaid pigem seda, et puudub algoritm, mis suudaks probleemi kiiresti lahendada.
Siin on lihtne näide. Seal on 100 palli, millele on kirjutatud erinevad juhuslikud numbrid.
– Ülesanne 1: Milline on pallidele kirjutatud numbrite maksimaalne väärtus?
– Ülesanne 2: Kas leidub pallide hulk, millele kirjutatud numbrite summa on 100?
Ülesande 1 puhul, kui võtate ühe palli välja ja asendate selle, kui selle number on suurem kui teie käes oleva palli number, on tulemuseks maksimaalne arv, mis tähendab, et peate tegema kokku 99 võrdlust. Võrdluseks, ülesande 2 puhul peame kontrollima, kas iga 100 palliga moodustatava kombinatsiooni korral on olemas hulk, mille summa on 100, mis tähendab, et halvimal juhul peame tegema umbes 2 astmes 100 arvutusi (* alamhulkade koguarv). See on kujuteldamatult pikk aeg, umbes 23 kvadriljonit aastat, isegi kui eeldada, et superarvuti teeb kvadriljon operatsiooni sekundis.
Algoritmi nimetatakse polünoomseks algoritmiks, kui pallide arvu (N) suurenedes ei ületa tehteid (N-1) pallide arvu polünoomfunktsiooni, nagu ülesande 1 lahenduses. Sellise algoritmi olemasolu võib olla määravaks teguriks lihtsa ja raske ülesande vahel.
P=NP?
Pane tähele, et keerulise ülesande 2 vastuse leidmine, mille jaoks polünoomse aja algoritmi ei eksisteeri, nõuab tohutul hulgal arvutusi, kuid vastuse õigsuse kontrollimine on väga lihtne. Arvestades pallide komplekti, peaks kuluma vähem kui 10 sekundit, et kontrollida, kas kirja pandud numbrite summa on 100. Teisisõnu, see, et ülesannet on lihtne arvutada, ei tähenda, et seda on lihtne lahendada. Kas selle lahendamiseks on lihtne viis ja matemaatikud pole seda veel leidnud või kas selle lahendamiseks pole üldse lihtsat viisi, jääb veel näha. See on P-NP ülesanne.
P-hulk on lihtsate ülesannete hulk, millele saab vastata polünoomse ajaga, näiteks ülesanne 1, ja NP-hulk on ülesannete hulk, mille õigsust saab polünoomse ajaga kontrollida. P-NP-ülesanne on ülesanne, mille puhul tõestatakse, kas P-hulk ja NP-hulk on samaväärsed hulgad. On iseenesestmõistetav, et P-hulk kuulub NP-hulka. Siiski pole veel tõestatud, et iga NP-hulga ülesanne kuulub P-hulka. Kui see on tõestatud, tähendab see, et igal hõlpsasti arvutataval ülesandel on hõlpsasti täidetav lahendus, st me ei vaja enam 10^28 aastat ülesande 2 lahendamiseks.
NP probleemid ja päris elu
P-NP-ülesande matemaatiline raskusaste ei tee sellest läbi aegade seitsme parima matemaatikaülesande hulka kuuluvat. Selle tõestamine on nii oluline seetõttu, et see on tihedalt seotud reaalsete probleemide lahendamisega. Reaalsed probleemid nii erinevates tööstusharudes nagu lennukite planeerimine, pooljuhtide disain, puurmasinate paigutamine, genoomsete andmete analüüs, astronoomiliste teleskoopide paigutamine ja röntgenkristallograafia on NP-rasked probleemid, mille lahendamine võtab kaua aega. Siiski pole me veel avastanud algoritmi optimaalsete otsuste kiireks langetamiseks ja me ei tea isegi, kas selline algoritm eksisteerib. Seega, kuidas me polünoom-aja algoritmi puudumisel praegu reaalsete probleemide kohta otsuseid langetame?
Erinevate valdkondade, näiteks matemaatika, arvutiteaduse, tööstustehnika jne teadlased uurivad ja arendavad erinevaid ligikaudseid lahendusi, mis on reaalsete probleemide optimaalseks lahenduseks ligikaudsed. Mõelge taas varga probleemile: kui optimaalse kalliskivide kombinatsiooni leidmine võtaks kaua aega, on alternatiiviks leida viis otsuste kiireks ja tõhusaks langetamiseks suhteliselt väikese kasumiga. Üks viis selleks võib olla iga kalliskivi väärtuse arvutamine kaalu kohta ja oma koti täitmine kõigepealt kalliskividega, millel on suurim väärtus kaalu kohta. Seda ligikaudset lahendust nimetatakse ahneks heuristikuks ja seda on praktikas kasutatud siis, kui otsuseid on vaja kiiresti langetada. Kuigi need lähendused ei ole optimaalsed, on need väga kasulikud otsuste langetamisel reaalsetes probleemides, millel on ajapiirangud. Lisaks muutuvad mõned ligikaudsed lahendused üha keerukamaks, mõned lähendused suudavad antud probleemi optimaalse väärtuse ligikaudselt määrata 0.5% vea piires.
Turvatööstus ja NP probleemid
Erinevalt ülaltoodud tööstusharudest on üks tööstusharu, mis ei soovi NP-probleemide lahendamiseks lihtsat algoritmi. See on turvatööstus. Praegused turvaskeemid on korraldatud nii, et NP-probleemi kasutatakse vastupidiselt. Kui teate parooli, on lihtne kontrollida, kas see on õige, kuid seda pole lihtne leida, sest selle leidmiseks puudub polünomiaalajastuses algoritm. Võib-olla loodab kogu turvatööstus, et P-NP-probleem jääbki igaveseks mõistatuseks.
Isegi kui P=NP on tõestatud, ei tähenda see, et kõik NP-ülesanded on kergesti lahendatavad. Siiski on selge, et polünoom-aja algoritmi olemasolu kannustab paljusid teadlasi uurima polünoom-aja algoritme raskete NP-ülesannete jaoks. Sellel on oluline mõju efektiivsuse parandamisele ja reaalsete probleemide optimeerimisele. Vastupidiselt, kui selgub, et P≠NP, tähendab see, et sellist meetodit pole olemas, mis tähendab, et paljud NP-ülesanded jäävad reaalses maailmas lahendamatuks. Igal juhul on huvitav näha, milline on selle mõistatuse tulemus.
