NP-komplette problemer og bevis

Én hardhet, mange forkledninger

Forrige kapittel forankret alt i Circuit-SAT: ett problem som ethvert problem i NP reduseres til. Nå skal vi se hardheten spre seg. Hver gang vi reduserer et kjent NP-komplett problem til et nytt, smitter NP-hardheten over på det nye — og siden reduksjoner komponerer, vokser familien av NP-komplette problemer som en kjedereaksjon fra én eneste gnist.

Oppskriften er den samme hver gang. ƒreduksjon for np-kompletthetsbevis For å vise at et problem $B$ er NP-komplett: vis først at $B$ ligger i NP ved å gi et sertifikat og en rask verifikator, og reduser så et allerede kjent NP-komplett problem $A$ til $B$. Hjertet i hvert bevis er korrektheten til reduksjonen: ƒkorrekt reduksjon. Begge retningene må argumenteres — det er her de fleste bevis faktisk gjør arbeidet.

SAT og veien til 3-CNF-SAT

En boolsk formel er bygd av variabler, negasjon, OG og ELLER. sat spør: finnes det en tilordning av sann/usann til variablene som gjør hele formelen sann? Et sertifikat er bare en slik tilordning, og å sjekke den er rask innsetting — så SAT er i NP. Fra Circuit-SAT følger at SAT også er NP-komplett. ƒcook-levin-teoremet

Beviset blir enklere å bygge videre på hvis formelen har en fast form. 3-cnf-sat krever konjunktiv normalform med nøyaktig tre literaler per klausul: en stor OG av små ELLER-klausuler, der hver klausul er tre literaler. Et eksempel:

(x₁ ∨ ¬x₂ ∨ x₃) ∧ (¬x₁ ∨ x₂ ∨ x₄) ∧ (x₂ ∨ ¬x₃ ∨ ¬x₄)

Reduksjonen $\mathrm{SAT}{\le }_p\text{3-CNF-SAT}$ omskriver en vilkårlig formel til denne formen uten å endre om den er tilfredsstillbar. Man bryter formelen ned i sitt syntakstre, innfører en frisk hjelpevariabel for hver delformel, og tvinger hjelpevariabelen til å være ekvivalent med delformelen ved hjelp av et lite knippe klausuler. Klausuler som blir for korte eller for lange, polstres eller splittes til de har akkurat tre literaler. Hele omskrivingen er lineær i formelens størrelse, altså polynomiell, og den bevarer tilfredsstillbarhet nøyaktig.

CLIQUE: fra logikk til graf

Nå skifter vi domene helt — fra formler til grafer — og det er her reduksjonenes virkelige magi blir synlig. clique spør om en graf inneholder en klikk av størrelse $k$: en mengde på $k$ noder der hver to av dem er forbundet med en kant.

Reduksjonen $\text{3-CNF-SAT}{\le }_p\mathrm{CLIQUE}$ bygger en graf ut av formelen ved hjelp av en gadget — en liten, gjenbrukbar byggekloss som etterligner en bit av kildeproblemet i målproblemets språk. Her er gadgeten per klausul enkel: for en formel med $k$ klausuler lager vi én node for hver literal i hver klausul, gruppert i $k$ små grupper. Så trekker vi en kant mellom to noder fra ulike grupper presist når literalene deres kan være sanne samtidig — det vil si når den ene ikke er negasjonen av den andre. Vi trekker bevisst aldri en kant innen samme gruppe.

Påstanden er: formelen er tilfredsstillbar hvis og bare hvis grafen har en klikk av størrelse $k$. Begge veier:

Tilfredsstillbar  ⇒  klikk:
  En tilfredsstillende tilordning gjør minst én literal sann i
  hver av de k klausulene. Velg én slik sann literal per klausul.
  Ingen to motsier hverandre (de er jo alle sanne samtidig),
  så alle parene er forbundet — det er en klikk på k noder.

Klikk  ⇒  tilfredsstillbar:
  En klikk på k noder må ta nøyaktig én node fra hver gruppe
  (ingen kanter finnes innen en gruppe). Sett hver tilhørende
  literal sann; ingen konflikt er mulig, siden alle parene har
  kant. Det gir en tilfredsstillende tilordning.

Begge retninger holder, grafen bygges i polynomiell tid, og dermed er CLIQUE NP-komplett. Eksempelet over med fire klausuler ville gitt en graf på tolv noder — for små til å tegne her, men poenget er konstruksjonen, ikke tallene.

VERTEX-COVER: samme sak, snudd

vertex-cover spør om det finnes en mengde på $k$ noder som dekker alle kantene: hver kant har minst én ende i mengden. CLIQUE og VERTEX-COVER er to sider av samme mynt, bundet sammen av komplementgrafen $\overline{G}$, som har samme noder men motsatte kanter. ƒclique og vertex-cover

Sammenhengen er ren: en mengde noder er en klikk i $G$ nettopp når de resterende nodene utgjør et toppunktdekke i $\overline{G}$. Det gir en reduksjon nesten uten arbeid — bygg $\overline{G}$ og spør etter et dekke av størrelse $|V|-k$ i stedet for en klikk av størrelse $k$. Ingen sinnrik gadget trengs; selve dualiteten er reduksjonen. Det er et reint eksempel på at en korrekt reduksjon noen ganger bare er en gjennomtenkt oversettelse av spørsmålet.

Hvorfor stemmer dette? Anta at $S$ er en klikk i $G$. Da finnes det per definisjon ingen kanter mangler inni $S$, og siden $\overline{G}$ har akkurat de kantene $G$ mangler, har $\overline{G}$ ingen kant med begge ender i $S$. Hver kant i $\overline{G}$ må altså ha minst én ende utenfor $S$ — det vil si i komplementmengden $V\setminus S$. Men «hver kant har en ende i $V\setminus S$» er nettopp definisjonen av at $V\setminus S$ dekker $\overline{G}$. Snur du argumentet, får du den andre retningen. En klikk på $k$ noder i $G$ svarer eksakt til et dekke på $|V|-k$ noder i $\overline{G}$, og omvendt. Her ser du hvorfor begge retninger må sjekkes: hadde bare den ene holdt, kunne reduksjonen sagt ja på en nei-instans og vært verdiløs som bevis.

Videre: HAM-CYCLE, TSP og SUBSET-SUM

Fra VERTEX-COVER fortsetter kjeden inn i grafer med struktur og inn i tall.

ham-cycle spør om en graf har en Hamiltonsk sykel: en rundtur som besøker hver node nøyaktig én gang og ender der den startet. Reduksjonen fra VERTEX-COVER er den mest gadget-tunge i kjeden. Hver kant i originalgrafen erstattes av en liten gjennomgangsdings på flere noder, konstruert slik at en Hamiltonsk sykel er tvunget til å gå gjennom dingsen på en av et fåtall lovlige måter — og de lovlige måtene koder nøyaktig hvilke noder som er med i dekket. Detaljene er fiklete, men ideen er den samme som før: oversett «velg $k$ dekkende noder» til «finn en sykel», bit for bit.

tsp, handelsreisendeproblemet, følger nesten gratis fra HAM-CYCLE. Ta grafen, gi hver eksisterende kant lengde 1 og hver manglende kant en stor lengde, og spør om det finnes en rundtur med total lengde høyst $|V|$.

HAM-CYCLE  ≤p  TSP:
  kant i grafen      →  avstand 1
  ingen kant         →  avstand stor (f.eks. |V| + 1)
  spør: rundtur med total lengde ≤ |V| ?

En rundtur på $|V|$ byer med lengde høyst $|V|$ kan bare bruke kanter av lengde 1 — altså ekte kanter i den opprinnelige grafen — og det er nøyaktig en Hamiltonsk sykel. Igjen: en svar-bevarende oversettelse, beregnbar i polynomiell tid.

subset-sum bryter ut av grafverdenen helt. Det spør om en delmengde av gitte heltall summerer til en målverdi $t$. Reduksjoner hit fra 3-CNF-SAT koder hver variabel og hver klausul som svære tall, sifferposisjon for sifferposisjon. Tanken er at hvert tall får én sifferkolonne per variabel og én per klausul. Velger du tallet som svarer til «$x_i$ sann», setter du et ettall i variabelkolonnen til $x_i$ og i kolonnene til alle klausulene den literalen tilfredsstiller. Målsummen $t$ velges slik at den tvinger fram nøyaktig én sannhetsverdi per variabel og minst én oppfylt literal per klausul — pluss noen polstringstall som tar opp slakk. At delmengden treffer $t$ på øret, betyr da at den koder en tilfredsstillende tilordning. Det viser hvor langt fra hverandre to NP-komplette problemer kan se ut — boolske formler og ren aritmetikk — og likevel være like harde, fordi en reduksjon binder dem sammen.

En siste advarsel hører med her. SUBSET-SUM er bare NP-hardt når tallene får lov til å være store, altså å ha mange siffer. Begrenser du målverdien til å være et lite tall, finnes det en kjapp tabellbasert algoritme — kjøretiden blir polynomiell i selve tallverdien, ikke i lengden av kodingen. Slike problemer kaller vi pseudopolynomielle, og de minner oss om hvorfor kjøretid alltid måles i kodingens lengde: et tall på $n$ siffer representerer verdier opp mot $2^n$, så «polynomiell i verdien» kan i hemmelighet være eksponentiell i inndatastørrelsen.

Hva kjeden faktisk gir oss

Hvert ledd i kjeden er én reduksjon, bevist korrekt begge veier og polynomiell. Transitiviteten gjør resten: når SAT er NP-komplett og SAT ${\le }_p$ 3-CNF-SAT ${\le }_p$ CLIQUE ${\le }_p$ VERTEX-COVER, er alle fire NP-komplette, og hardheten fortsetter ut til HAM-CYCLE, TSP og SUBSET-SUM. ƒreduksjonskjeden

Det praktiske utbyttet er en arbeidsvane. Står du overfor et nytt problem og mistenker at det er hardt, leter du ikke etter et bevis fra bunnen. Du leter etter et kjent NP-komplett problem som ligner, og prøver å bygge en gadget-basert reduksjon fra det til ditt. Lykkes du, har du spart deg selv for å jakte på en rask algoritme som nesten sikkert ikke finnes — og du har føyd ett ledd til den samme kjeden som startet med én boolsk krets.