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 begrepser 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 er en binær relasjon som er transitiv, det vil si:

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

Det vil si, hvis er mindre eller lik under preordningen , og er mindre eller lik , så er mindre eller lik . Med mindre vi presiserer at er en streng ordning, så antar vi også .

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

Dersom og sier vi at og er ekvivalente, og vi kan gruppere elementene i i ekvivalensklasser. Hvis er en slik klasse, så har vi altså både og for alle , som i følgende diagram:

Vi definerer et maksimum for som et element der for ethvert element . Det vil si, er et maksimum hvis alle elementer er mindre eller lik .

Tilsvarende er et minimum mindre eller lik alle andre, det vil si for ethvert element .

Merk at vi kan ha flere maksima og flere minima, men disse vil være ekvivalente! For eksempel, om og er maksima, så vet vi at for alle , inkludert om , så vi har . Tilsvarende har vi .

Kompletthet

Reduksjoner utgjør en preordning, der vi intuitivt sett ordner problemer etter hvor vanskelige de er. Hvis det finnes en reduksjon av passende type, så sier vi at ikke er vanskeligere enn . Vi kan ha reduksjoner begge veier, så og , 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 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 ekvivalensklassen av alle minima. Dersom vi skulle finne en reduksjon der er i NPC og 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.