Reduksjoner, ordning og kompletthet

Det kan være mye å ta inn over seg når man skal forstå det konseptuelle maskineriet rundt NP-kompletthet. For enkelte kan det kanskje være nyttig å se på ideen om kompletthet isolert, separat fra begreper som reduksjoner eller polynomisk kjøretid. Én måte å gjøre det på er å se på relasjonen «kan reduseres til», som er en såkalt preordning – en generalisering av både delvise ordninger og ekvivalensrelasjoner. Hva NP-kompletthet er, og hvorfor P = NP dersom det finnes en reduksjon fra NPC til P, er ting det fint går an å forstå kun ved å se på denne preordningen.

Preordninger

En preordning av en mengde \(S\) er en binær relasjon \(\to\) på \(S\) som er transitiv, det vil si:

\[x\to y\to z\implies x\to z\]

Om vi tenker på det som en graf, så har vi alle transitive kanter: Dersom det finnes en sti fra \(x\) til \(z\), så finnes det også en direkte kant:

Det vil si, hvis \(x\) er mindre eller lik \(y\) under preordningen \(\to\), og \(y\) er mindre eller lik \(z\), så er \(x\) mindre eller lik \(z\). Med mindre vi presiserer at \(\to\) er en streng ordning, så antar vi også \(x\to x\).

Intuitivt, så oppstår slike ordninger f.eks. om vi ordner ting etter en eller annen egenskap. For eksempel kan \(x\to y\) betyr at \(x\) ikke er høyere enn \(y\). Om vi da også har \(y\to z\), så vet vi at \(x\to z\). Men om vi også har \(y\to x\), så vet vi bare at \(x\) og \(y\) er like høye – ikke at de er samme person! Dvs., vi vet ikke at \(x=y\).

Dersom \(x\to y\) og \(y\to x\) sier vi at \(x\) og \(y\) er ekvivalente, og vi kan gruppere elementene i \(S\) i ekvivalensklasser. Hvis \(C\) er en slik klasse, så har vi altså både \(x\to y\) og \(y\to x\) for alle \(x,y\in C\), som i følgende diagram:

Vi definerer et maksimum for \(\to\) som et element \(t\in S\) der \(x\to t\) for ethvert element \(x\in S\). Det vil si, \(t\) er et maksimum hvis alle elementer er mindre eller lik \(t\).

Tilsvarende er et minimum \(s\) mindre eller lik alle andre, det vil si \(s\to x\) for ethvert element \(x\in S\).

Merk at vi kan ha flere maksima og flere minima, men disse vil være ekvivalente! For eksempel, om \(t_1\) og \(t_2\) er maksima, så vet vi at \(x\to t_1\) for alle \(x\in S\), inkludert om \(x=t_2\), så vi har \(t_2\to t_1\). Tilsvarende har vi \(t_2\to t_1\).

Kompletthet

Reduksjoner utgjør en preordning, der vi intuitivt sett ordner problemer etter hvor vanskelige de er. Hvis det finnes en reduksjon \(A\to B\) av passende type, så sier vi at \(A\) ikke er vanskeligere enn \(B\). Vi kan ha reduksjoner begge veier, så \(A\to B\) og \(B\to A\), som betyr at problemene er like vanskelige, men det betyr ikke at de er samme problem.

Ekvivalensklassene i ordningen gir oss eksempler på kompleksitetsklasser, og det å være et maksimum under ordningen tilsvarer det som kalles kompletthet.

For eksempel, om vi lar \(\to\) være preordningen gitt av polynomiske reduksjoner innen NP, så vil et maksimum være det samme som et NP-komplett problem, og NPC er ekvivalensklassen av alle maksima. Motsatt, så er \(P\) ekvivalensklassen av alle minima. Dersom vi skulle finne en reduksjon \(A\to B\) der \(A\) er i NPC og \(B\) er i P, så har vi (ved hjelp av transitivitet) etablert at hele NP er én og samme ekvivalensklasse, og at alle problemene er ekvivalente – og at P = NP = NPC.