Jag satt och surfade spännande artiklar på fantastiska arXiv och sprang på en märklig artikel.
Artikeln P is not equal to NP av Sten-Åke Tärnlund verkar hävda att den bevisar att P är skilt från NP.
Vad det handlar om är alltså den del av komplexitetsteori som säger att det antagligen finns problem som inte går att beräkna på polynomiell tid, dvs en separat klass med problem som för trivialt antal element inte går att beräkna svaret på. Det har länge spekulerats att NP inte är en del av P och frågan är av sådan betydelse att det finns ett pris på en miljon USD för den som kan visa att NP är skilt från P.
Skälet till att detta är så intressant för IT-säkerhet är att det finns ett antal algoritmer där säkerheten beror på att problemen är NP-hårda. Ett sådant problem är Knapsack-problemet som används i kryptosystem med publika nycklar. Över huvud taget görs ofta antaganden om att algoritmer är NP-hårda, och därmed att NP-problem egentligen inte är P-problem. Wikipedia ger ett bra exempel:
Consider, for instance, the subset-sum problem, an example of a problem which is “easy” to verify, but whose answer is believed (but not proven) to be “difficult” to compute. Given a set of integers, does some nonempty subset of them sum to 0? For instance, does a subset of the set {−2, −3, 15, 14, 7, −10} add up to 0? The answer “yes, because {−2, −3, −10, 15} add up to zero”, can be quickly verified with a few additions. However, finding such a subset in the first place could take much longer. The information needed to verify a positive answer is also called a certificate. Given the right certificates, “yes” answers to our problem can be verified in polynomial time, so this problem is in NP.An answer to the P = NP question would determine whether problems like the subset-sum problem are as “easy” to compute as to verify. If it turned out P does not equal NP, it would mean that some NP problems are substantially “harder” to compute than to verify.
Jag kan på tok för lite matte för att hänga med i Tärnlunds artikel. Den som fixar matten och kan kolla om det håller och om det gäller generellt eller ej får gärna höra av sig. Artikelns sammanfattning är kort och verkar hävda att generellt sett är P skilt från NP:
SAT !∈P is true, and provable in a simply consistent extension B′ of a first order theory B of computing, with a single finite axiomB characterizing a universal Turing machine. Therefore P !=NP is true, and
provable in a simply consistent extension B′′ of B.
SAT som artikeln hänvisar till är Boolean Satisfiability-problemet som tidigare visat sig vara NP-komplett. Det Sten-Åke verkat visa är hur detta resultat går att generalisera till alla NP-problem. Om jag fattar rätt.
Googlar jag på Sten-Åke Tärnlund hittar jag att han är (har varit?) professor i datalogi vid Uppsala universitet.
No related posts.
Related posts brought to you by Yet Another Related Posts Plugin.
Bakgrund:
Att ett problem tillhör NP betyder bara att om man får en lösning så går det att verifiera i polynomisk tid att det faktiskt är en lösning. Till exempel ligger sortering i NP eftersom man kan verifiera att en sorterad lista faktiskt är sorterad i polynomisk (till och med linjär) tid.
Att ett problem är NP-svårt (NP-hard) innebär att alla problem i NP kan reduceras till ditt NP-svåra problem (A kan reduceras till B innebär att A kan lösas med hjälp av en lösning till B). Observera att ett NP-svårt problem inte behöver ligga i NP. Generaliserat schack (givet ett schackspel med parametriserade regler, pjäser och utgångsposition, finns det då en idiotsäker metod för spelaren vid draget att vinna) är till exempel NP-svårt, men tillhör inte NP eftersom man inte generellt kan verifiera att en vinnande strategi är en vinnande strategi i polynomisk tid.
Att ett problem A är NP-fullständigt (NP-complete) innebär att det:
(1) Tillhör NP, visas vanligen genom att man visar att en lösning kan verifieras i polynomisk tid.
(2) Alla problem i NP kan reduceras till problem A. Man går vanligtvis via Cook’s sats (som säger att SAT är NP-fullständigt) och reducerar SAT till sitt problem A. Man kan även gå via något annat av de hundratals problem som bevisats vara NP-fullständiga.
För att bevisa att P!=NP på det sätt som bilden illustrerar så måste man visa att något av de kända NP-fullständiga problemen inte går att lösa i polynomisk tid.
För att visa att P=NP räcker det med att visa att SAT går att lösa i polynomisk tid.
Som jag tolkar Tärnlunds artikel så antar han att SAT tillhör P och visar att det leder till två motsägelsefulla slutsatser om beviskomplexitet. Alltså har vi motsägelse och P!=NP. Han försöker inte “generalisera [SAT] till alla NP-problem”.