Kompleksitetsklasser og NP-kompletthet

To slags «vanskelig»

Noen problemer kan vi løse raskt. Å sortere en million tall, finne korteste vei i et veinett, eller sjekke om en graf er sammenhengende — alt går unna på en brøkdel av et sekund selv for store inndata. Andre problemer virker prinsipielt verre. Skal du pakke en ryggsekk optimalt, planlegge en rundtur innom hundre byer, eller finne ut om et vaktskjema i det hele tatt lar seg fylle, har ingen funnet en metode som ikke før eller siden eksploderer i tid når inndataene vokser.

Dette kapittelet handler om å gjøre det skillet presist. Vi vil ikke bare ane at noe er hardt — vi vil kunne bevise at et problem er minst like hardt som en hel familie av andre. Verktøyet for det er kompleksitetsklasser og reduksjoner.

Beslutningsproblemer, koding og språk

For å sammenligne problemer rettferdig trenger vi en felles form. Vi reduserer alt til beslutningsproblemer: spørsmål med ja eller nei som svar. «Finnes det en rundtur kortere enn 500 km?» er et beslutningsproblem; «hva er den korteste rundturen?» er det ikke, men de to henger tett sammen, og det er nesten alltid nok å studere ja/nei-varianten.

En instans må representeres som en streng før en algoritme kan lese den. Den representasjonen kaller vi en koding. En graf kan kodes som en liste over kanter, et tall som sifre, en ryggsekk som en rad med vekter og verdier. Valget av koding spiller en rolle, for kjøretid måles alltid i lengden av kodingen — i hvor mange tegn det tar å skrive instansen ned, ikke i en eller annen «naturlig» størrelse. Så lenge vi holder oss til fornuftige, kompakte kodinger, endrer ikke detaljene konklusjonene våre.

Når hver ja-instans er en streng, kan vi samle alle ja-instansene i én mengde. Den mengden er et formelt språk: nettopp de strengene som koder et ja-svar. Da blir «å løse problemet» det samme som «å avgjøre om en gitt streng ligger i språket $L$». Dette mengde-perspektivet er grunnen til at vi senere kan skrive ting som $L\in \mathrm{P}$ eller $L^{\prime }{\le }_{p}L$ helt presist.

Klassen P: det vi greier raskt

Et problem ligger i klassen p hvis det finnes en algoritme som avgjør det i polynomiell tid — kjøretid $O(n^k)$ for en fast konstant $k$, der $n$ er lengden av kodingen. Formelt er P unionen over alle slike polynom-grader: ƒklassen p.

Hvorfor akkurat polynom? Fordi polynomer oppfører seg pent. Setter du to polynomielle algoritmer etter hverandre, eller bruker den ene som subrutine i den andre et polynomielt antall ganger, er resultatet fortsatt polynomielt. Den robustheten gjør P til en stabil definisjon av «praktisk løsbart», selv om en algoritme på $n^{10}$ i praksis er ubrukelig. Skillet vi er ute etter, er det grovere skillet mot eksponentiell tid som $2^n$, der selv $n=60$ er håpløst.

P har en nyttig egenskap til: den er lukket under komplement. ƒp er lukket under komplement Kan du avgjøre $L$ raskt, kan du avgjøre det motsatte spørsmålet like raskt — bare kjør samme algoritme og snu svaret til slutt. Det høres trivielt ut, men det blir interessant nettopp fordi det ikke er åpenbart at det samme gjelder for den neste klassen.

Klassen NP: det vi greier å sjekke raskt

Mange harde problemer har en eiendommelig asymmetri. Å finne en løsning virker dyrt, men å kontrollere en løsning noen rekker deg, er billig. Får du et forslag til rundtur, er det lett å summere lengden og sjekke at den er kort nok. Får du en tilordning av sannhetsverdier, er det lett å regne ut om formelen blir sann.

Det er denne ideen klassen np fanger. Et problem er i NP hvis hver ja-instans har et kort bevis — et sertifikat — som kan kontrolleres i polynomiell tid. Sertifikatet for rundturen er selve turen; sertifikatet for formelen er tilordningen. En verifikator er algoritmen som tar instansen og sertifikatet og sier ja hvis sertifikatet holder. ƒklassen np

Legg merke til den skjeve definisjonen: vi krever bare et sertifikat for ja-instansene. For et nei-svar — «det finnes ingen rundtur kortere enn 500 km» — kreves intet bevis. Den asymmetrien er hele poenget, og den er grunnen til at det er åpent om NP er lukket under komplement slik P er.

Hvert problem i P er også i NP: kan du løse det selv i polynomiell tid, trenger du ikke noe sertifikat — bare løs det og ignorer hintet. Så $\mathrm{P}\subseteq \mathrm{NP}$. Om inklusjonen er ekte eller om de to klassene egentlig er like, er det berømte p vs. np-spørsmålet, og det er ubesvart.

Reduksjoner: å oversette ett problem til et annet

For å rangere problemer etter hardhet trenger vi en måte å si «$A$ er ikke vanskeligere enn $B$». Det gjør vi med en polynomiell reduksjon, skrevet $A{\le }_{p}B$. En reduksjon er en funksjon $r$ som oversetter enhver $A$-instans $x$ til en $B$-instans $r(x)$, slik at svaret bevares: $x$ er en ja-instans for $A$ hvis og bare hvis $r(x)$ er en ja-instans for $B$. I tillegg må $r$ selv kunne beregnes i polynomiell tid.

Tankegangen er en oversettelse. Har du en rask algoritme for $B$, får du en rask algoritme for $A$ gratis: ta $A$-instansen $x$, oversett den til $r(x)$, kjør $B$-algoritmen, og rapporter svaret rett tilbake. Begge stegene er polynomielle, så hele prosedyren er det. Derfor leser vi $A{\le }_{p}B$ som «$A$ er minst like lett som $B$» — eller, snudd om, «$B$ er minst like hardt som $A$».

Reduksjoner komponerer: hvis $A{\le }_{p}B$ og $B{\le }_{p}C$, så $A{\le }_{p}C$, fordi to polynomielle oversettelser etter hverandre fortsatt er polynomiell. Den transitiviteten er motoren i hele neste kapittel.

NP-hardhet og NP-kompletthet

Nå kan vi gi «hardest mulig» en presis mening. Et problem $L$ er np-hard hvis alt i NP reduseres til det: ƒnp-hardhet. Et NP-hardt problem er en universalnøkkel — en rask algoritme for det ville gi en rask algoritme for hvert eneste problem i NP, via reduksjonen. Merk at et NP-hardt problem ikke trenger å ligge i NP selv; det kan til og med være uavgjørbart.

Når et problem er både NP-hardt og ligger i NP, kaller vi det np-komplett. ƒnp-kompletthet De NP-komplette problemene er de hardeste i NP, og de henger sammen som perler på en snor gjennom reduksjoner. Det gir oss en slående konklusjon: finner noen en polynomiell algoritme for bare ett eneste NP-komplett problem, faller alle de andre samtidig, og $\mathrm{P}=\mathrm{NP}$. Motsatt, hvis $\mathrm{P}\ne \mathrm{NP}$, har ingen av dem en polynomiell algoritme.

Det er denne alt-eller-ingenting-strukturen som gjør NP-kompletthet til et så kraftig praktisk verktøy. Beviser du at problemet ditt er NP-komplett, har du ikke bevist at det er umulig å løse — men du har vist at en effektiv løsning ville løst tusenvis av andre problemer som verdens skarpeste hoder har kjempet med i tiår. I praksis er det signalet til å slutte å lete etter den perfekte raske algoritmen og i stedet sikte på tilnærminger, heuristikker eller spesialtilfeller.

Slik beviser man at et problem er hardt

Hvordan viser man at noe er NP-hardt uten å sjekke alle uendelig mange problemer i NP? Svaret er reduksjonens transitivitet. Vi trenger bare ett problem som allerede er kjent NP-hardt. Da holder det å redusere det kjente problemet til vårt nye: er $A$ NP-hardt og $A{\le }_{p}B$, så arver $B$ hardheten fra alt som reduserte til $A$.

Men hele kjeden må forankres et sted. Det første problemet som ble bevist NP-komplett uten å støtte seg på et tidligere, er Circuit-SAT: spørsmålet om en boolsk krets av OG-, ELLER- og IKKE-porter kan gjøres til å sende ut 1 for et eller annet valg av innganger. Cook og Levin viste, ved å kode selve kjøringen av en vilkårlig polynomiell verifikator som en krets, at ethvert problem i NP reduseres til Circuit-SAT. Det er ankeret. Alt vi gjør i neste kapittel, henger til slutt fra den ene konstruksjonen.

Et lite skissert mønster for et NP-kompletthetsbevis ser slik ut:

For å vise at B er NP-komplett:
  1. Vis B ∈ NP
       gi et sertifikat og en polynomiell verifikator.
  2. Velg et kjent NP-komplett problem A.
  3. Konstruer en reduksjon r: instans av A  →  instans av B,
       beregnbar i polynomiell tid.
  4. Bevis korrekthet, begge veier:
       x er ja for A   ⇒  r(x) er ja for B
       r(x) er ja for B ⇒  x er ja for A

Steg 1 plasserer $B$ i NP; steg 2–4 viser at $B$ er NP-hardt. Til sammen: NP-komplett. Hver enkelt brikke er enkel å sjekke; styrken ligger i at de til sammen rangerer et helt landskap av problemer etter hardhet — uten at vi noensinne har klart å avgjøre om landskapet egentlig kollapser inn i P.