7.2 Polynomiske reduksjoner og reduksjonsretning

Polynomisk reduksjon `≤ₚ`, den kritiske **retningen** (`A ≤ₚ B` ⇒ B minst like vanskelig), NP-hardt vs. NP-komplett, og `P=NP`-konsekvensen.

55 min

6 oppgaver

Polynomiske reduksjonerreduksjonsretning

Din fremgang i kapitlet

0 / 6 oppgaver

Kapitlets plass i kurset

Bygger på

7.1P, NP og co-NP — sertifikat og verifikasjon

Brukes videre i

7.3NP-komplette problemer

NP-teori og reduksjoner er registrert i alle de 17 settene i grunnlaget
(100 %). Grunnlaget er de 17 settene fra august 2015 til august 2023 som er
gjennomgått tema for tema — det er nevneren hver gang boka oppgir en prosent.
Bare to andre temaer er like sikre: asymptotisk notasjon og sortering.

Og innenfor dette temaet finnes ett spørsmål som går igjen mer enn noe annet:
hvilken vei går reduksjonen, og hva beviser den?

Sjangeren er én:

- Sjanger G — reduksjon og argument om vanskelighet, altså at du sier
hvilken vei et argument går, hva det viser, og — like viktig — hva det
ikke viser. Svarformen er to til fire linjer.

Høyeste prioritet — dette må sitte. Løsningsforslagene fremhever
reduksjonsretningen som skillet mellom riktig og galt oftere enn noe annet
enkeltpunkt i faget.

Regelen i én linje, før vi begynner: for å vise at ditt problem er
vanskelig, reduserer du FRA et kjent vanskelig problem TIL ditt. Går
pilen motsatt vei, har du bevist ingenting om at ditt problem er vanskelig.

Slik er kapitlet lagt opp (55 min):

Innhold	Tid
Hva en polynomisk reduksjon er	ca. 14 min
Retningen — kapitlets kjerne	ca. 16 min
NP-hardt og NP-komplett	ca. 12 min
Pseudopolynomisk mot eksponentiell	ca. 13 min

Forkunnskaper

- kap. 7.1 — P, NP og sertifikat. Fra det kapitlet:
et avgjørelsesproblem har ja/nei-svar. Klassen P er de problemene som
kan løses i polynomisk tid; klassen NP er de der et ja-svar kan
kontrolleres i polynomisk tid, gitt et sertifikat. Det er kjent at
$P \subseteq NP$ , og det er åpent om de er like.
- kap. 5.2 — pseudopolynomisk. Dette sto der: en
algoritme er pseudopolynomisk når kjøretiden er polynomisk i
tallverdiene i inputen, men ikke i inputens lengde.
Ford-Fulkerson er $O(E\cdot\lvert f^*\rvert)$ , og en kapasitet på $10^9$
tar 30 binære siffer å skrive, men kan gi en milliard runder. Det sier
ingenting om at maks-flyt er vanskelig — Edmonds-Karp løser problemet i
$O(VE^2)$ . Vi henter det skillet fram igjen mot slutten av kapitlet, i en
situasjon der konklusjonen blir en annen.
- kap. 6.2 — 0-1-ryggsekk med $\Theta(nW)$ , der $W$ er
en tallverdi.

Ett nytt problem innføres underveis, SUBSET-SUM, fordi det er det klareste
eksempelet på skillet mellom pseudopolynomisk og eksponentiell. Katalogen over
de øvrige NP-komplette problemene kommer i
kap. 7.3.

Notasjons- og pseudokodeliste

Hva en polynomisk reduksjon er (~14 min)

En kommune har allerede et fungerende system for å sette opp vaktlister. Så
kommer et nytt problem: å fordele møterom. I stedet for å bygge noe nytt
oversetter de romproblemet til et vaktlisteproblem, kjører det gamle systemet,
og oversetter svaret tilbake.

Det er nøyaktig en reduksjon. Du løser $A$ ved hjelp av en løser for $B$ ,
og prisen er oversettelsen.

Det avgjørende for oss er ikke at teknikken er praktisk. Det er hva den
forteller om de to problemene når oversettelsen er billig.

Polynomisk reduksjon

A \le_p B

Hva reduksjonen gir deg

A \le_p B

✏️Eksempel 1: En reduksjon, ledd for ledd

KLIKK-3 er problemet: gitt en urettet graf

G

, finnes det tre noder som
alle er parvis forbundet med hverandre?

TREKANT er problemet: gitt en urettet graf $G$ , inneholder $G$ en trekant?

Vis at KLIKK-3 $\le_p$ TREKANT, og gjennomgå de tre kravene.

Oversettelsen.

f(G) = G

. Grafen sendes videre uendret.

Det ser ut som juks, men det er en helt gyldig reduksjon — og den illustrerer
kravene tydelig nettopp fordi oversettelsen er triviell.

Krav 1 — polynomisk tid. Å kopiere grafen koster $\Theta(V+E)$ . Oppfylt.

Krav 2 — svarbevaring begge veier. Tre noder som er parvis forbundet, er
en trekant, og en trekant er tre parvis forbundne noder. Altså:

$G \text{ har en 3-klikk} \iff G \text{ har en trekant}$

Oppfylt, og legg merke til at begge retningene må sjekkes. Hadde $f$ bare
garantert den ene veien, kunne en nei-instans blitt oversatt til en ja-instans,
og svaret ville vært galt.

Krav 3 — definert for alle instanser. Enhver graf kan sendes videre.
Oppfylt.

Hva reduksjonen forteller. TREKANT kan løses i $O(V^3)$ ved å prøve alle
tripler av noder. Siden KLIKK-3 $\le_p$ TREKANT, arver KLIKK-3 den samme
grensen: oversett i lineær tid, kjør TREKANT-løseren.

Konklusjonen går altså denne veien: $B$ er lett, derfor er $A$ lett.

Det motsatte følger ikke. At KLIKK-3 reduseres til TREKANT, sier ingenting
om at TREKANT skulle være vanskelig. Det er nettopp den forvekslingen resten av
kapitlet handler om.

📝Oppgave 1

(Innstegsoppgave, sjanger D — definisjon med egne ord, altså én presis setning
med hovedpoenget først.)

Forklar hva $A \le_p B$ betyr, og list de tre kravene til en gyldig reduksjon.

Retningen — kapitlets kjerne (~16 min)

Nå kommer det ene punktet dette kapitlet finnes for.

Reduksjonen $A \le_p B$ er ikke symmetrisk. Den sier noe om forholdet mellom
de to problemene, og den sier det i én bestemt retning.

📜Retningsregelen

Påstanden.

A \le_p B

betyr at $B$ er minst like vanskelig som $A$ .

Hvorfor. Reduksjonen gir deg en oppskrift: løs $A$ ved å oversette og kjøre
$B$ -løseren. Er $B$ lett, blir $A$ lett. Altså kan ikke $A$ være vanskeligere
enn $B$ — opp til polynomisk arbeid.

De to leserettene.

$A \le_p B \;\text{og}\; B \in P \;\Longrightarrow\; A \in P \qquad\text{(lettheten flyter bakover)}$

$A \le_p B \;\text{og}\; A \notin P \;\Longrightarrow\; B \notin P \qquad\text{(vanskeligheten flyter framover)}$

Den andre er den kontrapositive formen av den første, og den er den du
bruker: for å vise at et problem $X$ er vanskelig, viser du
$A \le_p X$ for et kjent vanskelig $A$ .

Regelen for eksamen, i én setning:

For å vise at X er vanskelig, reduserer du FRA et kjent vanskelig
problem TIL X.

Og den motsatte veien? $X \le_p A$ med $A$ kjent vanskelig, viser at $X$
ikke er vanskeligere enn $A$ . Det er en øvre grense, og den er nesten
alltid uinteressant — for eksempel er ethvert problem i NP reduserbart til
et NP-komplett problem, så påstanden er triviell.

Dette er felle #1 — den mest fremhevede feilen i hele faget.

✏️Eksempel 2: Fire påstander, fire ulike svar

For hver av påstandene: hva følger, og hva følger ikke? Anta at 3-CNF-SAT
er kjent NP-komplett.

a) «Jeg har vist 3-CNF-SAT $\le_p$ X.»
b) «Jeg har vist X $\le_p$ 3-CNF-SAT.»
c) «Jeg har vist X $\le_p$ Y, og Y kan løses i $O(n^3)$ .»
d) «Jeg har vist 3-CNF-SAT $\le_p$ X og at X ligger i NP.»

a) X er NP-hardt. Reduksjonen går fra et kjent vanskelig problem til X,
så X er minst like vanskelig som 3-CNF-SAT.

Følger ikke: at X er NP-komplett. Det krever i tillegg at X ligger i NP, og
det er en egen påstand som må vises for seg.

b) Ingenting om at X er vanskelig. Reduksjonen viser at X ikke er
vanskeligere enn 3-CNF-SAT — altså at X ligger i NP, siden 3-CNF-SAT gjør det.

Merk hvor svak påstanden er: hvert eneste problem i NP kan reduseres til
et NP-komplett problem. Å vise denne retningen er derfor nesten alltid
bortkastet.

c) X kan løses i polynomisk tid. Lettheten flyter bakover: oversett i
polynomisk tid, kjør Y-løseren. Den samlede kjøretiden er polynomisk.

Følger ikke: noe om Y sin vanskelighet. At noe kan reduseres til Y, gjør ikke
Y hardt.

d) X er NP-komplett. Dette er et fullstendig NPC-bevis: NP-hardhet fra
reduksjonen, og medlemskap i NP fra den andre delen.

Mønsteret å ta med seg: reduksjonspilen peker alltid mot det som er
minst like vanskelig. Les den høyt: «jeg reduserer fra det vanskelige til
mitt problem, altså er mitt problem minst like vanskelig».

📝Oppgave 2

Eksamensnivå, sjanger G

Du har vist SAT $\le_p$ X.

a) Hva forteller det om X sin vanskelighet?
b) Hva forteller det ikke?
c) Hva mangler for at X skal være NP-komplett?

📝Oppgave 3

Eksamensnivå, sjanger G

En kandidat skriver: «Jeg har vist at problemet mitt SKIFTPLAN kan reduseres
til 3-CNF-SAT. Siden 3-CNF-SAT er NP-komplett, er SKIFTPLAN NP-hardt.»

Er argumentet gyldig? Svar ja eller nei, og forklar hva som er galt.

NP-hardt og NP-komplett (~12 min)

De to begrepene brukes om hverandre i dagligtale, og det er en av de tre
feilene løsningsforslagene retter oftest. Skillet er enkelt når det først er
sagt.

NP-hardt

X

NP-komplett

et problem er NP-komplett (NPC) når det er NP-hardt og ligger i NP . De NP-komplette problemene er de vanskeligste i NP, og de står og faller sammen: løser du ett i polynomisk tid, løser du alle. Et NPC-bevis har alltid to deler, og de er uavhengige: medlemskapsdelen (gi et sertifikat) og hardhetsdelen (reduser fra et kjent NPC-problem).

📜

P=NP

-konsekvensen

Påstanden. Finnes det en polynomisk algoritme for ett eneste
NP-komplett problem

X

, så er

P = NP

Argumentet, kort. La $A$ være et vilkårlig problem i NP. Siden $X$ er
NP-hardt, finnes en polynomisk reduksjon $A \le_p X$ . Sett sammen: oversett
$A$ -instansen i polynomisk tid, kjør den polynomiske $X$ -algoritmen. Det gir en
polynomisk algoritme for $A$ . Siden $A$ var vilkårlig, ligger hele NP i P, og
sammen med $P \subseteq NP$ fra kap. 7.1 gir det
$P = NP$ .

Den kontrapositive formen er den nyttige: tror du $P \ne NP$ , tror du også
at ingen NP-komplett problemer har polynomiske algoritmer. Det er derfor et
NPC-bevis i praksis leses som «slutt å lete etter en rask eksakt algoritme».

Hva teoremet ikke sier. Det sier ingenting om hvorvidt $P = NP$ er sant.
Spørsmålet er åpent.

📝Oppgave 4

Eksamensnivå, sjanger F

Ta stilling til hver av påstandene:

a) Ethvert NP-hardt problem er NP-komplett.
b) Ethvert NP-komplett problem er NP-hardt.
c) Finner noen en polynomisk algoritme for CLIQUE, følger $P = NP$ .
d) Et NP-hardt problem må være et avgjørelsesproblem.

Pseudopolynomisk mot eksponentiell (~13 min)

Til slutt et skille som ser ut som en teknikalitet, men som er et av fagets
faste innsiktsspørsmål — og som er lett å trekke feil konklusjon av i begge
retninger.

SUBSET-SUM

S

Inputstørrelse for tallproblemer

t

Pseudopolynomisk

\Theta(n\,t)

Felle #7 — pseudopolynomisk sier ingenting om vanskelighet i seg selv

Dette er felle #7, og den er nummer to på løsningsforslagenes liste over
gjentatte feil.

Fellen går i begge retninger, og begge er feil:

- «Algoritmen er pseudopolynomisk, altså er problemet NP-hardt.» Galt.
Ford-Fulkerson er pseudopolynomisk, men maks-flyt ligger i P — se
kap. 5.2. Egenskapen ved algoritmen sier ingenting
om problemet.
- «Problemet har en $\Theta(nt)$ -algoritme, altså kan det ikke være
NP-komplett.» Også galt. SUBSET-SUM har nettopp en slik algoritme og er
likevel NP-komplett, fordi $t$ ikke er inputstørrelsen.

Den riktige måten å si det på:

Algoritmen er pseudopolynomisk: kjøretiden er polynomisk i tallverdiene, men
ikke i inputens lengde. Om problemet er hardt, avgjøres av et helt annet
argument — en reduksjon.

Kontrollen: står ordet «pseudopolynomisk» i svaret ditt, skal setningen
etter handle om algoritmen, ikke om problemet.

✏️Eksempel 3: Samme algoritme, to konklusjoner

To problemer har hver sin DP-algoritme der en tallverdi inngår i
kjøretiden:

- maks-flyt med Ford-Fulkerson: $O(E\cdot\lvert f^*\rvert)$ ;
- SUBSET-SUM med DP over målsummen: $\Theta(n\,t)$ .

Begge algoritmene er pseudopolynomiske. Likevel ligger det ene problemet i P og
det andre er NP-komplett.

Forklar hvorfor det ikke er en selvmotsigelse.

Det de har felles. Begge kjøretidene inneholder en tallverdi —

\lvert f^*\rvert

t

— som kan være enorm selv når instansen er kort å
skrive ned. Begge algoritmene er derfor pseudopolynomiske, og begge kan bruke
eksponentiell tid målt i inputens lengde.

Hvorfor maks-flyt likevel ligger i P. Fordi det finnes en annen
algoritme: Edmonds-Karp med $O(VE^2)$ , der ingen tallverdi inngår. Et problem
ligger i P så snart minst én polynomisk algoritme finnes — det kreves ikke
at alle er polynomiske.

Hvorfor SUBSET-SUM er NP-komplett. Fordi 3-CNF-SAT reduseres til det (se
kap. 7.3), og fordi det ligger i NP. Ingen har funnet
en algoritme uten tallverdien i kjøretiden — og finner noen én, følger
$P = NP$ .

Det som avgjør, er altså ikke algoritmen, men reduksjonen.

$\text{pseudopolynomisk algoritme} \;\not\Longrightarrow\; \text{hardt problem}$
$\text{pseudopolynomisk algoritme} \;\not\Longrightarrow\; \text{lett problem}$

Svarformen på eksamen: to til fire linjer. «Pseudopolynomisk er en egenskap
ved algoritmen: kjøretiden er polynomisk i tallverdiene, ikke i inputens
lengde. Problemets vanskelighet avgjøres av reduksjoner, ikke av at én
algoritme tilfeldigvis har denne formen — maks-flyt ligger i P til tross for
Ford-Fulkerson, og SUBSET-SUM er NP-komplett til tross for
$\Theta(n\,t)$ -algoritmen.»

📝Oppgave 5

Eksamensnivå, sjanger G

En kandidat skriver: «SUBSET-SUM kan løses i $\Theta(n\,t)$ med dynamisk
programmering. Det er polynomisk i $n$ og $t$ , så SUBSET-SUM ligger i P. Altså
har jeg vist at $P = NP$ .»

Hvor svikter argumentet? Svar presist.

📝Oppgave 6

Eksamensnivå, sjanger…

Et firma har problemet PAKKEPLAN: gitt $n$ pakker med heltallsvekter og $k$
biler med lik kapasitet, kan alle pakkene fordeles på bilene?

a) Skisser hvordan du ville vist at PAKKEPLAN er NP-hardt.
b) Skisser medlemskapsdelen.
c) En kollega finner en DP-algoritme med kjøretid $\Theta(n\,W)$ , der $W$
er kapasiteten. Motsier det a)?

Typiske feil

Den første er fagets mest fremhevede feil.

- Å reversere reduksjonsretningen. Dette er felle #1. For å vise at X
er vanskelig, reduserer du FRA et kjent vanskelig problem TIL X. Den
motsatte veien viser bare at X ikke er vanskeligere — og det er sant for
hvert eneste problem i NP.
- Å blande NP-hardt og NP-komplett. NP-komplett er «NP-hardt og i NP».
Et NPC-bevis har to uavhengige deler, og reduksjonen dekker bare den ene.
- Å blande pseudopolynomisk og NP-hardt. Felle #7, i begge retninger.
Egenskapen ved algoritmen sier ingenting om problemet.
- Å glemme at reduksjonen må bevare svaret begge veier. «Hvis og bare
hvis». En oversettelse som bare garanterer den ene retningen, kan gjøre en
nei-instans om til en ja-instans.
- Å glemme at oversettelsen må være polynomisk. Er $f$ dyr å regne ut,
faller hele argumentet — sammensetningen er ikke lenger polynomisk.
- Å redusere et spesialtilfelle. Å vise at ditt problem løser en spesiell
variant av et NPC-problem, holder ikke. Reduksjonen må dekke alle
instanser.
- Å konkludere at et NP-hardt problem er umulig å løse. Det finnes
eksakte algoritmer, de er bare ikke polynomiske. Og
approksimasjonsalgoritmer finnes for mange av dem.

Og den gjennomgående: å ikke si hva reduksjonen ikke viser. I sjanger G er
det halve svaret.

Oppslagstabellen for sjanger G

Du har vist	Da følger	Da følger ikke
$A \le_p X$ med $A$ NP-komplett	X er NP-hardt	at X er NP-komplett (medlemskap mangler)
$X \le_p A$ med $A$ NP-komplett	X ligger i NP	noe som helst om at X er hardt
$A \le_p X$ og X i NP	X er NP-komplett	at X er umulig å løse
$X \le_p Y$ og Y i P	X ligger i P	noe om Y sin vanskelighet
X er NP-komplett og X i P	$P = NP$	at $P = NP$ faktisk er sant
Algoritmen for X er pseudopolynomisk	ingenting om X sin vanskelighet	verken at X er hardt eller lett

Én presisering som er verdt å ta med seg. Alle radene leses fra venstre mot
høyre, og alle bygger på den samme ene setningen: pilen peker mot det som er
minst like vanskelig. Kan du lese pilen riktig, kan du hele tabellen.

Begrepsbank

Begrepsbanken er flashcard- og repetisjonsstoff — den gjentar det du nettopp
har lest. Hopp trygt over ved førstegangslesing; tidsanslaget for kapitlet
gjelder kjernestoffet.

Polynomisk reduksjon

A \le_p B

Retningsregelen

A \le_p B

Hva en reduksjon ikke viser

X \le_p A

NP-hardt

alle problemer i NP kan reduseres polynomisk til problemet. Vises i praksis ved å redusere ett kjent NP-komplett problem til det. Trenger ikke selv ligge i NP — et NP-hardt problem kan være mye vanskeligere, og trenger ikke være et avgjørelsesproblem.

NP-komplett

NP-hardt og i NP. De vanskeligste problemene i NP; de står og faller sammen. Beviset har to uavhengige deler: sertifikat og verifikasjon for medlemskapet, og en reduksjon for hardheten.

P=NP

-konsekvensen

P = NP

De tre kravene til en reduksjon

1. oversettelsen regnes ut i polynomisk tid; 2. svaret bevares begge veier; 3. den er definert for alle instanser. Alle tre er ledd som gir uttelling. Krav 3 er den skjulte fellen: en reduksjon som bare dekker et spesialtilfelle, beviser ingenting.

Kontrapositiv bruk

A \le_p B

SUBSET-SUM

\Theta(n\,t)

Inputstørrelse

t

Pseudopolynomisk

O(E\cdot\lvert f^*\rvert)

Felle #1 — reversert reduksjonsretning

å redusere til et NP-komplett problem og tro at det viser at ditt problem er hardt. Det viser bare at ditt problem ligger i NP — sant for hvert eneste NP-problem. Fagets mest fremhevede feil. Les pilen høyt før du leverer.

Felle #7 — pseudopolynomisk mot NP-hardt

å slutte fra en pseudopolynomisk algoritme til et hardt problem, eller fra en pseudopolynomisk algoritme til et lett problem. Begge slutningene er ugyldige. Problemets vanskelighet avgjøres av reduksjoner, aldri av at én algoritme tilfeldigvis har en tallverdi i kjøretiden.

Sjanger G — reduksjon og argument om vanskelighet

oppgavetypen der du skal si hvilken vei et argument går, hva det viser, og hva det ikke viser. Svarformen er to til fire linjer: retningen, konsekvensen, og forbeholdet. Registrert i alle de 17 settene i grunnlaget — dette er den sikreste sjangeren i faget.

Å lese reduksjonen høyt

kontrollen du gjør før du leverer: «jeg reduserer FRA TIL, altså er mitt problem minst like vanskelig». Stemmer ikke setningen, går pilen feil vei. Tar fem sekunder og redder fagets dyreste feil.

Repetisjonsoppgaver

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.

Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Norges teknisk-naturvitenskapelige universitet. Dette er ikke offisielt studiemateriell. Les mer.