Komplexitetsklasser

För en som är pragmatiskt lagd ter sig många diskussioner inom den teoretiska datavetenskapen avlägsna och, ärligt talat, rätt oviktiga. Särskilt när inlämningsuppgifter och tentor hänger som orosmoln över sinnet.

Men när skolan väl är avklarad går det sen att konsumera valfria, mer teoretiska, delar av ämnet bit för bit i sin egen takt. Ett återkommande tema är komplexitetsklasser, men ingen verkar kunna förklara dem på ett enkelt sätt. Här är mitt ödmjuka försök.

Algoritm

En algoritm är en beräkningsmetod för att lösa ett problem. Vår algoritm tar en sträng av ettor och nollor som input och levererar ett svar som output. Målet är att ta reda på ungefär hur lång tid det kommer ta att räkna ut svaret. Tiden beskrivs i termer av hur antalet beräkningar påverkas av antal bitar i inputen. Antalet beräkningar kan t.ex. vara antalet varv i algoritmens inre loop (eller antalet multiplikationer etc). Det viktiga är inte exakt hur en beräkning definieras, utan i vilken takt antalet beräkningar ökar när bitlängden i inputen ökar. Antalet bitar betecknas med bokstaven n och förhållandet till antal beräkningar brukar skrivas med ett grekiskt \mathcal{O} (uttalas Ordo, eng. big-O notation) fölt av ett uttryck av n. T.ex. \mathcal{O}(n^2). Det betyder då att antalet steg ökar med kvadraten på antalet bitar i inputen. Detta kan t.ex. hända om algoritmens hjärta består av två nästlade loopar som båda har ungefär samma storleksordning som n.

Polynomisk tid, P

Om antalet beräkningssteg kan beskrivas som ett polynom av n tillhör problemet som algoritmen löser klassen P (för Polynomisk tid).

Några exempel:

\mathcal{O}(1)      ; Grymt, beror inte ens på n
\mathcal{O}(n)      ; Mycket bra
\mathcal{O}(n \log n) ; Bra
\mathcal{O}(n^2)     ; Inte så bra
\mathcal{O}(n^3)     ; Dåligt

Icke (deterministisk) Polynomisk tid, NP

Som synes finns olika svårighetsgrader även inom P. Men för att klassas som NP behöver n hamna i exponenten. Exempel:

\mathcal{O}(2^n) --> NP <-- ; Katastrof

Nu växer antalet steg snabbt bara n ökas lite grann. Redan efter 100 bitar eller så är antalet steg astronomiskt och det skulle ta tusentals år att köra algoritmen även på en snabb dator. Algoritmer med n uppe i exponenten sägs ta exponentiell tid och hamnar i NP (Non-deterministic Polynomial).

Ickedeterministisk betyder egentligen en algoritm som alltid väljer ”rätt väg” när den står inför ett vägval, utan att på förhand känna till den rätta vägen?! För att klassas som ett NP problem ska en icke-deterministisk algoritm kunna lösa problemet i polynomisk tid (i teorin, i praktiken är det dock svårt att skriva ett program som alltid väljer rätt gren utan att på förhand veta vilken gren som är rätt).

Ytterligare ett krav på ett NP-problem är att om ett svar finns, ska det vara ”enkelt” att kontrollera svaret (inom polynomisk tid).

Ett exempel på ett NP-problem är att faktorisera stora heltal. Den bästa kända algoritmen (som kan köras på en klassisk dator) är General Number Field Sieve som har ungefär \mathcal{O}(2^{n^{\frac{1}{3}}}). Det är visserligen bättre än brute force – \mathcal{O}(2^{n}) – men ligger ändå i NP eftersom n är uppe i exponenten. Känner man till primtalsfaktorerna av ett stort tal är det dock enkelt att multiplicera ihop dem för att kontrollera om svaret stämmer. Det är för övrigt denna asymmetri som kryptosystemet RSA bygger på (kallas trapdoor-funktion, svårt i ena riktningen men lätt i den andra, förutsatt att man känner till ”hemligheten”).

Kvantdator

I teorin går det att bygga en kvantdator. Den baserar sig på ett märkligt fenomen kallat interferens mellan små partiklar (t.ex. fotoner eller elektroner). Tänk interferens som vågor på vattnet, som ibland släcker ut varandra och ibland förstärker varandra. Genom att konstruera interferensmönster så att endast regioner som stämmer med ett svar på en viss fråga förstärks, och resten släcks, kan kvantdatorn i teorin räkna ut svaret på frågan mycket snabbt. Frågan är bara för vilka frågor det går att konstruera sådana interferensmönster. 1994 kom Peter Shor på Shor’s algoritm. Med den kan en kvantdator (om den skulle existera*) faktorisera stora heltal i \mathcal{O}(n^2) steg. Även närliggande problem, som diskreta logaritmer och Elliptic Curve går att knäcka med varianter av Shor’s algoritm (mer specifikt, alla kryptosystem baserade på abelska grupper). En kvantattack är däremot inte lika effektiv mot symmetriska algoritmer (som AES, där nyckelstorlekar > 128 bitar går säkra**) eller mot kryptosystem baserade på Lattice.

P \neq NP ?

En intressant aspekt med Shor’s algoritm är att den förflyttade problemet med faktorisering av stora heltal från klassen NP till klassen P. Kan det finnas algoritmer som uppfinns i framtiden, som kan förflytta fler problem mellan dessa klasser? Kanske t.o.m. alla problem? Den frågan i sig är ett öppet problem. Ingen har hittills kunnat hitta ett enda problem som kan bevisas ligga i NP men inte i P. För den som kan presentera ett sådant bevis finns t.o.m. ett fint litet pris på $1M att hämta.

Överkurs: ännu fler klasser

NPC (NP-Complete) är en klass av problem som kan översättas till ett vanligt NP-problem (alla t.o.m.) inom polynomisk tid. Med andra ord, om man hittar en lösning till ett NPC problem kan samtidigt lösningen till de underliggande NP-problemen återskapas. Som om inte det vore nog finns även NPH (NP-Hard) problem. Om en lösning till ett NPH problem hittas, så påträffas samtidigt lösningen till ett NPC problem (inom polynomisk tid) och därmed även lösningen till alla NP-problem. Inte illa 😉 ”Enklare” problem inom NP kallas NP-easy eller NP-equivalent. Exempel. NPC problem: Hamilton Path. NPH: Subset Sum. Följ länkarna på wikipedia för fler exempel.

Komplexitetsklasser

Konsekvenser av om P skulle vara skilt från eller lika med NP

Problem som kan lösas med en kvantdator klassificeras för övrigt som BQP och BQP är definitivt större än P (eftersom t.ex. faktorisering ligger i BQP men inte i P) men det är inte känt om BQP fyller upp hela NP (det är inte ens känt om P fyller upp hela NP, många experter på området tror att P inte fyller upp hela NP, men detta kvarstår att bevisa).

Länkar

Petting Zoo – Introduktion till komplexitet

* Företaget D-Wave har sålt vad de påstår vara en fungerande kvantdator till bl.a. Google. Trots en enorm hype vet dock ingen riktigt vad D-Waves kvantmaskin är kapabel till. Inom den offentliga forskningen har man lyckats faktorisera talet 21 (resultatet 7*3, med en sannolikhet som överstiger 50%, vilket gör att svaret kan verifieras med en traditionell dator och experimentet upprepas igen och igen tills ett korrekt svar kommer ut). Det är inte så imponerande. Förmodligen dröjer det ett tag innan en praktiskt användbar kvantdator kommer kunna byggas. Då menar jag en kvantdator som är snabbare än, låt säga, min laptop, åtminstone på någonting.

** Grovers algoritm reducerar antalet steg till 2^\frac{n}{2}. Det betyder att aes-128 skulle ta 2^{64} steg att knäcka med en kvantdator, vilket är ”på gränsen” till säkert. Aes-256 däremot skulle ta 2^{128} steg med Grover och en hypotetisk kvantdator, vilket anses vara säkert med god marginal.

Advertisements

Om albertveli

Grävande programmerare.
Det här inlägget postades i Krypto, Matematik, Programmering. Bokmärk permalänken.

Kommentera

Fyll i dina uppgifter nedan eller klicka på en ikon för att logga in:

WordPress.com Logo

Du kommenterar med ditt WordPress.com-konto. Logga ut / Ändra )

Twitter-bild

Du kommenterar med ditt Twitter-konto. Logga ut / Ändra )

Facebook-foto

Du kommenterar med ditt Facebook-konto. Logga ut / Ändra )

Google+ photo

Du kommenterar med ditt Google+-konto. Logga ut / Ändra )

Ansluter till %s