7.3 NP-kompletthet — og hva som IKKE er IN2010-pensum

P og NP, verifikator/sertifikat og reduksjonsretning — pluss en avgrensning av de tunge TDT4120-temaene (DP, maks-flyt, masterteoremet) som er fraværende i IN2010.

55 min

7 oppgaver

NP-kompletthethva som IKKE er IN2010-pensum

Din fremgang i kapitlet

0 / 7 oppgaver

Kapitlets plass i kurset

Bygger på

1.4Kjøretids- og teori-fakta — sant/usant og antigjettings-strategi

Brukes videre i

7.PPrøver til del 7: Datastruktur-design, drøfting og NP-teori 8.1DRILL — Del 2-strategi: velg lavest kjøretid (poengtrappen) og skriv presis pseudokode

NP-stoffet er med i 4 av 7 sett (57 %), men frekvensen er fallende: det
var tungt i de fire eldste settene (2018 til 2021) og har vært fraværende i de
tre nyeste (2022 til 2024). Sjangeren er

- Sjanger L — NP-kompletthet, altså at du svarer på faste fakta om
klassene $P$ og $NP$ , skriver en verifikator som kontrollerer et foreslått
svar, eller vurderer hvilken vei en reduksjon må gå.

Prioritet: kjenne (nivå 3 av tre — «må sitte» er nivå 1, «kunne» er nivå 2).
Det betyr ikke «hopp over». Det betyr at stoffet er lite, at det kan komme, og at
det er billig å sikre: kommer det, kommer det nesten alltid som sant/usant på
Del 1, den auto-rettede delen av eksamen, og der er faktapunktene faste og få.

Verifikator-oppgaven som Del 2-oppgave er belagt i ett sett — høsten 2020,
som var korona-hjemmeeksamen med alle hjelpemidler. Den formen speiler ikke
dagens eksamen, så bruk verifikatoren først og fremst som et middel til å forstå
hva $NP$ betyr, ikke som en oppgavetype du må regne med.

Kapitlet har en jobb til, og den er kanskje viktigere: det siste avsnittet
sier hvilke tunge algoritmetemaer som ikke er pensum i dette emnet. Leser du
en generisk algoritmebok, eller snakker du med noen som har tatt et
algoritmeemne ved en annen institusjon, risikerer du å bruke uker på stoff som
aldri kommer på denne eksamen. Den avgrensningen er verdt like mye som
NP-teorien.

Slik er kapitlet lagt opp (55 min): fire løkker, med et pausepunkt etter
løkke 2. C er en god og vanlig karakter, og de faste faktapunktene her er blant
de enkleste poengene i hele faget.

Forkunnskaper

- kap. 1.4 — der møtte du klassene $P$ og $NP$ , sertifikat
og verifikator, og de faste sant/usant-punktene. Dette kapitlet bygger direkte
videre: her skal du skrive verifikatoren og bruke reduksjonsregelen.
- kap. 1.1 — vekstordningen, og særlig skillet mellom
polynomisk vekst som $n^2$ og eksponentiell vekst som $2^n$ . Hele
kompleksitetsteorien hviler på den ene grensen.
- kap. 5.1 — grafer, nabolister og nabomatrise. Alle
eksemplene under er grafproblemer, og verifikatoren slår opp i en av de to
representasjonene.
- kap. 3.1 — mod N-regningen. Den kommer tilbake her, i
den siste kanten av en rundtur.

Notasjons- og pseudokodeliste

Løkke 1 — å finne mot å kontrollere (ca. 12 min)

En bemanningsansvarlig setter opp turnus for 40 sykepleiere. Hver har sperrede
datoer, noen kan ikke gå vakt sammen, og hver vakt trenger minst én med
spesialkompetanse. Å finne en turnus som oppfyller alt kan ta dager.

Men får hun en ferdig turnus i hånda, tar det noen minutter å kontrollere den:
gå gjennom hver vakt, sjekk bemanningen, sjekk sperrene. Kontrollen er rask selv
om letingen var langsom.

Hele kompleksitetsteorien i dette kapitlet handler om det skillet. Det finnes
problemer der vi ikke kjenner noen rask måte å finne svaret på, men der enhver
foreslått løsning kan kontrolleres raskt. Det er nettopp de problemene klassen
$NP$ samler.

Å løse mot å kontrollere

P

Polynomisk tid

O(n^k)

Klassen NP — kontroll, ikke løsning

NP

📜De faste fakta om P og NP

Dette er punktene som kommer på Del 1, den auto-rettede delen, når NP-stoffet
først kommer. De er få, og de er faste.

Påstand	Svar
$P \subseteq NP$	sant
Finnes det en verifikator med polynomisk kjøretid, ligger problemet i $NP$	sant
Alle NP-komplette problemer kan reduseres til hverandre i polynomisk tid	sant
Løser du ett NP-komplett problem i polynomisk tid, følger $P = NP$	sant
Det er bevist at $P = NP$	usant
Det er bevist at $P \neq NP$	usant
Alle avgjørelsesproblemer ligger i $P$ eller i $NP$	usant
$NP$ betyr «ikke-polynomisk»	usant

Merk at listen blander sant og usant omtrent likt. Det gjør de ekte
sant/usant-blokkene også — det finnes ikke noe mønster å lene seg på, og det er
hele hensikten med antigjettings-skaleringen: en poengregning som skalerer
summen så ren gjetting i snitt gir null.
De to siste linjene er verdt et blikk til. Det finnes problemer som verken er i

P

eller i

NP

— for eksempel problemer der selv en foreslått løsning ikke kan
kontrolleres raskt. Og «

NP

» er en forkortelse mange leser feil, med den følgen
at de svarer «usant» på

P \subseteq NP

📝Oppgave 1

(Innstegsoppgave, sjanger L — NP-kompletthet, altså at du svarer på faste fakta
om $P$ og $NP$ , skriver en verifikator eller vurderer en reduksjonsretning.)
Marker sant eller usant, og skriv én setnings begrunnelse for hver.

a) Et problem i $P$ ligger også i $NP$ .
b) $NP$ er samlingen av problemer som ikke kan løses i polynomisk tid.
c) Det er bevist at $P \neq NP$ .
d) Finnes det en verifikator med polynomisk kjøretid for et problem, ligger
problemet i $NP$ .

Løkke 2 — sertifikatet og verifikatoren (ca. 16 min)

Turnusen bemanningsansvarlig fikk i hånda, er et sertifikat: et konkret
forslag til svar. Prosedyren hun kjører for å kontrollere det, er en
verifikator.

Kravet for at et problem skal ligge i $NP$ , er at det finnes en verifikator med
polynomisk kjøretid. Å skrive en slik prosedyre er en oppgavetype i seg selv,
og den er lettere enn den ser ut: du skal ikke løse problemet, bare kontrollere
et ferdig forslag.

Det klassiske eksempelet er Hamiltonsykel: finnes det en rundtur i en graf
som besøker hver node nøyaktig én gang og ender der den startet? Ingen kjenner
noen rask måte å finne en slik rundtur på. Men får du en foreslått rundtur, er
kontrollen triviell — nesten.

Sertifikatet

Det foreslåtte ja-svaret som verifikatoren får utlevert sammen med inndata. For Hamiltonsykel er det et array C med alle nodene i den rekkefølgen rundturen går; for en klikk er det listen over nodene i klikken. Sertifikatet må selv være av polynomisk størrelse. Et «sertifikat» som består av alle mulige rundturer, hjelper ingen — det er like stort som problemet.

Verifikatorens kontrakt

NP

Hamiltonsykel

Spørsmålet om det finnes en rundtur i en graf som besøker hver node nøyaktig én gang og vender tilbake til startnoden. Problemet er NP-komplett, og det er bokas standardeksempel av to grunner: sertifikatet er lett å beskrive (nodene i rekkefølge), og verifikatoren er kort nok til å skrives ut på eksamen. Forveksle det ikke med et spenntre eller en korteste vei — der finnes det raske algoritmer.

📜Pseudokode-kontrakt: `VerifiserHamiltonsykel`

Antagelser om representasjon. Den urettede grafen

G = (V, E)

er gitt som
nabomatrise, slik at ErKant(G, u, v) er

O(1)

N

er antall noder.
Sertifikatet C er et array med noder, indeks fra 0. Hjelpearrayet sett har én
plass per node.

Prebetingelse: ingen — verifikatoren skal tåle et hvilket som helst
sertifikat, også et ugyldig. Postbetingelse: returnerer sant nøyaktig når C
er en rundtur som besøker hver node én gang og lukker seg.

Procedure VerifiserHamiltonsykel(G, C)
  Input:  urettet graf G som nabomatrise med N noder,
          sertifikat C: array med noder, indeks fra 0
  Output: sant hvis C er en Hamiltonsykel i G, ellers usant

  if lengden av C er ulik N:
      return usant

  for hver node v i V:
      sett[v] = usant
  for i = 0 til N-1:
      if sett[C[i]]:
          return usant            // samme node to ganger
      sett[C[i]] = sant

  for i = 0 til N-1:
      u = C[i]
      v = C[(i + 1) mod N]        // ved i = N-1 gir dette C[0]
      if ErKant(G, u, v) er usant:
          return usant

  return sant

Grunnideen i én setning: en rundtur er nøyaktig tre ting — riktig antall
noder, ingen node to ganger, og en kant mellom hvert par som følger etter
hverandre, også mellom den siste og den første.

Kjøretid: tre løkker etter hverandre, hver over $N$ elementer, med $O(1)$
arbeid inni. Det gir $O(N)$ når grafen er en nabomatrise. Med nabolister koster
hvert kantoppslag opptil $O(N)$ , så verifikatoren blir $O(N^2)$ — fortsatt
polynomisk, og det er alt definisjonen krever.

Den ene linjen alt henger på er C[(i + 1) mod N]. Uten mod N stopper
løkka etter det nest siste paret, og en «rundtur» som ikke lukker seg, blir
godkjent. Det er felle #7 i bokas feilregister — å glemme siste kant i en
syklisk struktur.

✏️Eksempel 1: Verifikatoren kjørt på to sertifikater

En urettet graf har nodene $P$ , $Q$ , $R$ , $S$ , $T$ og kantene $P$ – $Q$ , $Q$ – $R$ ,
$R$ – $S$ , $S$ – $T$ , $T$ – $P$ og $P$ – $R$ . Nabolistene er

P: Q, R, T
Q: P, R
R: P, Q, S
S: R, T
T: P, S

Kjør VerifiserHamiltonsykel på de to sertifikatene
$C_1 = (P, Q, R, S, T)$ og $C_2 = (Q, P, R, S, T)$ , og oppgi svaret for hver.

Begge sertifikatene har lengde 5, som er $N$ , og begge inneholder hver node
nøyaktig én gang. De to første kontrollene passerer altså i begge tilfeller, og
det er kantløkka som avgjør.

Sertifikat 1: $C_1 = (P, Q, R, S, T)$

Steg `i`	Par `(C[i], C[(i+1) mod N])`	Er det en kant?	Status
0	`(P, Q)`	ja	fortsett
1	`(Q, R)`	ja	fortsett
2	`(R, S)`	ja	fortsett
3	`(S, T)`	ja	fortsett
4	`(T, P)` — siste par, `(i+1) mod N` gir 0	ja	fortsett

Svar: sant.

C_1

er en Hamiltonsykel. Fem kantoppslag, ett per node.
Sertifikat 2: $C_2 = (Q, P, R, S, T)$

Steg `i`	Par `(C[i], C[(i+1) mod N])`	Er det en kant?	Status
0	`(Q, P)`	ja	fortsett
1	`(P, R)`	ja	fortsett
2	`(R, S)`	ja	fortsett
3	`(S, T)`	ja	fortsett
4	`(T, Q)` — siste par, `(i+1) mod N` gir 0	nei	avvist

Svar: usant.

C_2

er ikke en Hamiltonsykel.
Se nøye på hva som skiller de to.

C_2

er en helt gyldig sti gjennom alle
fem nodene —

Q

til

P

til

R

til

S

til

T

, hvert steg langs en kant. Den

eneste feilen er at den ikke kommer hjem: det finnes ingen kant fra $T$ tilbake

til $Q$ .

Fellenote. En verifikator uten mod N i siste steg ville godkjent $C_2$ . Den
ville sjekket parene 0 til 3, funnet alle i orden, og returnert sant. Det er
felle #7, og den er dokumentert som en av de vanligste i denne oppgavetypen —
nettopp fordi den bare gir feil svar på de sertifikatene som ligner mest på et
riktig svar.
Merk også hvorfor kjøretiden er poenget. Kontrollen gjorde fem kantoppslag.
Å finne en Hamiltonsykel i samme graf ville i verste fall krevd at man prøvde

alle rekkefølger av de fem nodene. At kontrollen er $O(N)$ mens letingen ikke har

noen kjent polynomisk algoritme — det er hele innholdet i påstanden «Hamiltonsykel
ligger i $NP$ ».

📝Oppgave 2

Sjanger L

Bruk samme graf som i eksempel 1: nodene $P$ , $Q$ , $R$ , $S$ , $T$ og
kantene $P$ – $Q$ , $Q$ – $R$ , $R$ – $S$ , $S$ – $T$ , $T$ – $P$ , $P$ – $R$ .

a) Kjør verifikatoren på sertifikatet $(P, Q, R, P, T)$ . Hvilken av de tre
kontrollene stopper den, og hvorfor?
b) Kjør verifikatoren på sertifikatet $(P, R, S, T)$ . Hva skjer?
c) Finn selv et sertifikat som verifikatoren godkjenner, og som ikke er
$(P, Q, R, S, T)$ .

Den siste kanten i en rundtur

C[(i + 1) mod N] — uttrykket som gjør at siste steg i løkka sammenligner den siste noden med den første . Uten mod N sjekker verifikatoren en sti, ikke en sykel, og godkjenner sertifikater som ikke lukker seg. Det er felle #7 i bokas feilregister, og den gjelder like mye i alle andre sykliske gjennomganger: (i + 1) mod N er samme regning som i lineær probing i kap. 3.1 .

📝Oppgave 3

Sjanger L

En klikk i en urettet graf er en mengde noder der alle par
er naboer. Problemet CLIQUE spør: finnes det en klikk med $k$ noder?

a) Hva er sertifikatet, og hvilke antagelser om representasjon gjør du?
b) Skriv VerifiserKlikk i pseudokode.
c) Oppgi kjøretiden, og forklar hvorfor den viser at CLIQUE ligger i $NP$ .

— naturlig pausepunkt —

Så langt har du de faste faktapunktene og verifikatoren. De to siste løkkene er
kortere: én om hvilken vei en reduksjon må gå, og én om hva du ikke trenger å
lese.

Løkke 3 — reduksjonsretningen (ca. 14 min)

Tenk deg at du har en maskin som løser problem $B$ lynraskt. Du står med et
problem $A$ du ikke får til. Hvis du kan skrive om enhver $A$ -oppgave til en
$B$ -oppgave — raskt — så kan du bruke maskinen til å løse $A$ også.

Det er nøyaktig hva $A \leq_p B$ betyr. Og legg merke til hva den slutningen
sier: $B$ er minst like vanskelig som $A$ . Maskinen som løser $B$ , løser
nemlig $A$ på kjøpet.

Retningen er alt i denne sjangeren, og den er lett å snu feil vei fordi begge
formuleringene høres fornuftige ut når du sier dem fort.

Reduksjonen

A \leq_p B

A

📜Reduksjonsretningen — regelen, skrevet ut begge veier

Regelen: for å vise at et nytt problem

X

er vanskelig, reduserer du fra
et kjent vanskelig problem til

X

. Altså: kjent-vanskelig

\leq_p X

Skrevet ut som resonnement:

- Riktig vei. Vi vet at Hamiltonsykel er NP-komplett. Vi skriver om enhver
Hamiltonsykel-oppgave til en $X$ -oppgave i polynomisk tid. Da ville en rask
løser for $X$ gitt en rask løser for Hamiltonsykel. Altså er $X$ minst like
vanskelig som Hamiltonsykel. $X$ er vanskelig.
- Feil vei. Vi skriver om enhver $X$ -oppgave til en Hamiltonsykel-oppgave.
Da ville en rask løser for Hamiltonsykel gitt en rask løser for $X$ . Det viser
at $X$ ikke er vanskeligere enn Hamiltonsykel — altså at $X$ er minst like
lett. Om $X$ selv er vanskelig, sier det ingenting.

Huskeregelen i seks ord: reduser fra det vanskelige, til ditt eget.

At retningen er lett å snu, er ingen unnskyldning — den er felle #8 i bokas
feilregister, og det er trukket eksplisitt for den i arkivet. Til gjengjeld
gjelder også det motsatte: en reduksjon som er godt beskrevet, kan gi full
uttelling selv om kandidaten har snudd retningen, fordi resonnementet ellers
viser forståelse. Det er sensorpraksis, ikke en oppfordring.

✏️Eksempel 2: Eksamensnivå — en reduksjon skrevet ut, og den samme snudd feil vei

Et vaktselskap definerer problemet RUNDE-MED-BUDSJETT: gitt et sett poster,
en gangtid mellom hvert par av poster, og et tidsbudsjett $B$ — finnes det en
runde som besøker hver post nøyaktig én gang, ender der den startet, og bruker
til sammen høyst $B$ ?

Vis at RUNDE-MED-BUDSJETT er minst like vanskelig som Hamiltonsykel.

Ledd 1 — hvilken vei. Vi skal vise at det nye problemet er vanskelig, så
vi reduserer fra det kjente vanskelige problemet til det nye:
Hamiltonsykel

\leq_p

RUNDE-MED-BUDSJETT.

Ledd 2 — omskrivningen. Vi får en graf $G$ med $N$ noder og skal avgjøre om
den har en Hamiltonsykel. Vi bygger en RUNDE-MED-BUDSJETT-forekomst slik:

- hver node i $G$ blir en post,
- for hvert par poster settes en gangtid: 1 hvis paret er en kant i $G$ ,
og 2 hvis det ikke er det,
- tidsbudsjettet settes til $B = N$ .

Ledd 3 — hvorfor svaret blir det samme. En runde besøker $N$ poster og går
$N$ strekninger. Bruker den bare strekninger som koster 1, blir totalen nøyaktig
$N$ ; bruker den én eneste strekning til 2, blir totalen minst $N + 1$ .

Altså: det finnes en runde innenfor budsjettet $N$ hvis og bare hvis det
finnes en runde som bare bruker kanter fra $G$ — og det er nøyaktig en
Hamiltonsykel i $G$ .

Ledd 4 — at omskrivningen er polynomisk. Vi setter én gangtid per par poster,
altså $N(N-1)/2$ tall, hvert avgjort med ett kantoppslag. Omskrivningen er
$O(N^2)$ , som er polynomisk.

Konklusjon. Hamiltonsykel $\leq_p$ RUNDE-MED-BUDSJETT, så
RUNDE-MED-BUDSJETT er minst like vanskelig som Hamiltonsykel. Kunne vi løst
RUNDE-MED-BUDSJETT i polynomisk tid, kunne vi løst Hamiltonsykel i polynomisk
tid.

---

Og her er den samme oppgaven besvart feil vei — en midtnivåbesvarelse:

«Jeg reduserer RUNDE-MED-BUDSJETT til Hamiltonsykel: gitt en
RUNDE-med-budsjett-forekomst lager jeg en graf der jeg legger inn en kant
nøyaktig der gangtiden er 1. Da svarer Hamiltonsykel på grafen ja hvis og bare
hvis det finnes en runde innenfor budsjettet. Altså er RUNDE-MED-BUDSJETT
vanskelig.»

Hva som er bra nok: omskrivningen er faktisk gjennomtenkt og korrekt
beskrevet — kanter der gangtiden er 1 — og kandidaten har sett sammenhengen
mellom de to problemene. Sensorpraksis er at en godt beskrevet reduksjon gir
uttelling selv når retningen er snudd, så dette er ikke en nullbesvarelse. Det er
en ekte midtnivåbesvarelse.

Hva som mangler: slutningen i siste setning følger ikke. Det som er vist, er
RUNDE-MED-BUDSJETT $\leq_p$ Hamiltonsykel, altså at RUNDE-MED-BUDSJETT ikke er
vanskeligere enn Hamiltonsykel. Å oversette et problem til noe vanskelig gjør
ikke problemet vanskelig — du kan alltid oversette et lett problem til et
vanskelig.

Rettelsen er én setning: bytt om hva som er inndata og hva som konstrueres.
Start med en Hamiltonsykel-forekomst, bygg en RUNDE-forekomst av den, som i
besvarelsen over. Alt annet i besvarelsen kan stå.

Poengtrapp-notat. Hovedmomentet er retningen, og det gir mest. Deretter
kommer konstruksjonen, så argumentet for at svaret blir det samme begge veier
(«hvis og bare hvis»), og til slutt at omskrivningen er polynomisk. Det siste
leddet glemmes ofte, og det er en reell del av definisjonen — en omskrivning som
selv tar eksponentiell tid, viser ingenting.

📝Oppgave 4

Sjanger L

Marker sant eller usant, og begrunn hver med én setning.

a) Hvis vi reduserer vårt problem $X$ til et NP-komplett problem, har vi
vist at $X$ er NP-hardt.
b) Hvis $A \leq_p B$ og $B$ kan løses i polynomisk tid, kan $A$ løses i
polynomisk tid.
c) Alle NP-komplette problemer kan reduseres til hverandre i polynomisk tid.
d) En reduksjon som selv tar eksponentiell tid, er like god så lenge
omskrivningen er korrekt.

Reduksjonsretningen

X

NP-hard mot NP-komplett

NP

Konsekvensen av å løse ett NP-komplett problem

P = NP

CLIQUE

k

Knapsack og Sudoku

n \times n

Løkke 4 — hva som ikke er pensum her (ca. 10 min)

Denne bolken er den korteste i kapitlet og kanskje den mest lønnsomme. Den
handler om hva du ikke skal lese.

IN2010 er et datastruktur-tungt implementasjonsemne. Tyngdepunktet ligger på å
håndkjøre strukturer feilfritt og skrive presis pseudokode for graf-, tre- og
hashing-algoritmer. Flere av de temaene som fyller kapitler i en generisk
algoritmebok — og som er kjernestoff i algoritmeemner ved andre institusjoner —
er ikke en del av dette emnet.

Det er ikke det samme som at de er uviktige i faget algoritmer. Det betyr at de
ikke testes her, og at timene er bedre brukt et annet sted.

Fem temaer som ikke testes i dette emnet. Ingen kapittel i denne boka bygger på
dem, og de har ikke vært på noen av de sju settene i arkivet.

- Dynamisk programmering. Teknikken med å bygge opp en tabell av delløsninger
— ryggsekkproblemet, lengste felles delsekvens, myntveksling. Dette er en tung
bolk i mange algoritmeemner, og den er fraværende her.
- Maks-flyt. Flytnettverk og Ford-Fulkerson-metoden, med snitt og
restnettverk. Ikke pensum.
- Masterteoremet og rekurrensligninger. Metoden for å løse
$T(n) = aT(n/b) + f(n)$ . Kjøretidsanalyse i dette emnet gjøres ved
løkketelling — se kap. 1.2 — og rekursive algoritmer
analyseres ved å telle arbeidet per nivå eller si «hver node besøkes én gang».
- Floyd-Warshall. Alle-par-korteste-vei ved en trippelnøstet løkke over
mellomnoder. Korteste vei her er BFS, Dijkstra, Bellman-Ford og
DAG-metoden — se kap. 6.2.
- Gale-Shapley. Algoritmen for stabil matching mellom to grupper. Ikke
pensum.

Hvorfor dette står i boka: en student som leser en generisk algoritmebok fra
perm til perm, eller som følger et pensum fra et algoritmeemne ved en annen
institusjon, kan bruke uker på nettopp disse fem. De er velskrevne, de er
vanskelige, og de føles som kjernestoff. Her gir de null poeng.

Og motsatt vei — dette er tyngre her enn du kanskje tror:

- Hashing med lineær probing er med i 7 av 7 sett (100 %), og testes både
som håndkjøring og som pseudokode. I flere andre algoritmeemner er hashing et
faktapunkt; her er det en utførelsesferdighet. Se
kap. 3.1 og kap. 3.3.
- AVL-rotasjoner håndkjøres, med krav om antall enkle rotasjoner og rotverdi.
Se kap. 4.3.

Timene du sparer på listen over, er godt brukt på de to punktene her.

📝Oppgave 5

Sjanger L

Du har fire kvelder igjen før eksamen og finner en algoritmebok med
disse fem kapitlene igjen ulest. Ranger dem etter forventet poengutbytte på
eksamen i dette emnet, og begrunn kort.

a) «Flytnettverk og maks-flyt»
b) «Hashtabeller: åpen adressering og lineær probing»
c) «Rekurrensligninger og masterteoremet»
d) «Balanserte søketrær: AVL og rød-svart»
e) «Dynamisk programmering: ryggsekk og lengste felles delsekvens»

Typiske feil

- Å reversere reduksjonsretningen. Å redusere ditt problem til noe
NP-komplett beviser ingenting om ditt problems vanskelighet. Reduser fra det
vanskelige. Felle #8, og eksplisitt trukket for i arkivet.
- Å glemme siste kant i rundturen. En verifikator uten (C[N-1], C[0]), altså
uten mod N i siste steg, godkjenner stier som ikke lukker seg. Felle #7.
- Å tro at $P = NP$ eller $P \neq NP$ er avgjort. Begge påstandene om at noe
er bevist, er usanne. Dette er det aller enkleste punktet i bolken, og det er
også det som oftest kommer.
- Å forveksle $NP$ med «ikke i $P$ ». $P \subseteq NP$ , så alle de lette
problemene ligger også i $NP$ . Forkortelsen betyr «ikke-deterministisk
polynomisk», ikke «ikke-polynomisk».
- Å glemme at omskrivningen i en reduksjon må være polynomisk. Det er en del
av definisjonen, ikke en detalj — og det er det leddet som oftest mangler i
ellers riktige besvarelser.
- Å la verifikatoren lete etter et svar. En verifikator som prøver
alternativer, er ikke en verifikator. Den får sertifikatet utlevert og
kontrollerer det, én gjennomgang.
- Å kopiere rundtur-løkka inn i en klikk-verifikator. En klikk krever at
alle par er naboer, ikke bare de som følger etter hverandre — og der finnes
ingen mod N.

📝Oppgave 6

Sjanger L, eksamensnivå

En student skriver:

«Jeg har funnet en algoritme som løser CLIQUE på grafer med under 30 noder på
under ett sekund. Siden CLIQUE er NP-komplett, har jeg dermed vist at
$P = NP$ .»

a) Hva er galt med slutningen?
b) Hva ville faktisk vært nok til å vise $P = NP$ ?
c) Hva ville det betydd for de andre NP-komplette problemene?

📝Oppgave 7

Sjanger L

For hvert problem: er det i $P$ , er det NP-komplett, eller kan det
ikke avgjøres av det som står i oppgaven? Begrunn med én setning.

a) Finnes det en sti fra $u$ til $v$ i en urettet graf?
b) Finnes det en rundtur som besøker hver node nøyaktig én gang?
c) Finnes det et spenntre med totalvekt under $B$ ?
d) Finnes det en mengde på $k$ noder der alle par er naboer?

Begrepsbank

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

De vanligste sant/usant-fellene om P og NP

NP

Verifikatorens tre kontroller for en rundtur

N

Hvorfor verifikatoren må være polynomisk

NP

Utenfor IN2010-pensum

Fem temaer som ikke testes i dette emnet, og som ingen kapittel i boka bygger på: dynamisk programmering, maks-flyt (Ford-Fulkerson), masterteoremet og rekurrensligninger, Floyd-Warshall, og Gale-Shapley. De er kjernestoff i flere andre algoritmeemner og fyller store deler av en generisk algoritmebok. Her gir de null poeng. Kjøretidsanalyse gjøres ved løkketelling.

Tyngre her enn i en generisk algoritmebok

Hashing med lineær probing: 7 av 7 sett (100 %), testet både som håndkjøring og som pseudokode med mod N -wraparound. AVL-rotasjoner: håndkjøres, med krav om antall enkle rotasjoner og rotverdi. Begge undervurderes systematisk av studenter som kommer fra et annet algoritmepensum, der de er faktapunkter snarere enn utførelsesferdigheter.

Repetisjon — kapitlet på ett kort

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 Universitetet i Oslo. Dette er ikke offisielt studiemateriell. Les mer.