7.3 NP-komplette problemer

De navngitte NPC-problemene og beviset for at CIRCUIT-SAT er NP-komplett (kretsen simulerer en verifikator).

50 min

9 oppgaver

NP-komplette problemer

Din fremgang i kapitlet

0 / 9 oppgaver

Kapitlets plass i kurset

Bygger på

7.2Polynomiske reduksjoner og reduksjonsretning

Brukes videre i

7.4DRILL — Reduksjonsretning og NP-argumenter

NP-katalogen er den delen av pensum som kommer igjen oftest av alt.

- Sjanger D — definisjon med egne ord, altså at du gir én presis setning som fanger hovedpoenget først, og sjanger G — reduksjon og NP-argument, altså at du oppgir hvilken vei reduksjonen går og hva den beviser, er begge til stede i 100 % (17 av de 17 settene i grunnlaget).
- Dette kapitlet har høyeste prioritet — dette må sitte.

Det du trenes på her, er én ting: å kunne skrive ned den formelle definisjonen av hvert av de åtte navngitte problemene, som et ja/nei-spørsmål. Løsningsforslagene godtar mange formuleringer, men de godtar ikke et svar som bare gjentar navnet. Skriver du «CLIQUE handler om å finne en klikk», har du sagt null. Skriver du «gitt en graf $G=(V,E)$ og et tall $k$ : finnes det en mengde på minst $k$ noder der alle er parvis naboer?», har du svart.

Regn med to til fire oppgaver per sett som treffer stoffet i dette kapitlet, spredt på definisjoner og på spørsmål om hva en reduksjon beviser. De er blant de billigste sikre poengene i hele faget, fordi svaret er kort og fasiten entydig.

Forkunnskaper

Dette kapitlet bygger på kap. 7.1 og kap. 7.2. Dette sto der, og det brukes på hver eneste side under:

- NP er klassen av avgjørelsesproblemer der et ja-svar kan verifiseres i polynomisk tid gitt et sertifikat — et forslag til løsning som en verifikasjonsalgoritme sjekker. NP sier ingenting om hvor lang tid det tar å finne løsningen. Og $P \subseteq NP$ : alt du kan løse raskt, kan du også verifisere raskt.
- En polynomisk reduksjon $A \le_p B$ er en funksjon som gjør om enhver $A$ -instans til en $B$ -instans i polynomisk tid, slik at svaret er det samme: ja blir ja, og nei blir nei. Retningen betyr at $B$ er minst like vanskelig som $A$ .
- Derfor: for å vise at et problem $X$ er vanskelig, reduserer du fra et kjent vanskelig problem til $X$ . Motsatt vei beviser ingenting om $X$ sin vanskelighet.

Trenger du å friske opp mengdenotasjonen bak $G=(V,E)$ og $C \subseteq V$ , ligger den i Mengdelære.

Notasjons- og pseudokodeliste

Åtte problemer du skal kunne definere (~10 min)

En kommune skal sette sammen et vurderingspanel. Noen av de aktuelle fagpersonene har jobbet så tett sammen at de er inhabile overfor hverandre; resten kan sitte sammen. Spørsmålet fra rådmannen er enkelt nok: finnes det et panel på minst fem personer der ingen to er inhabile overfor hverandre?

Ingen i den samtalen sier ordet «graf». Men spørsmålet er allerede et av de åtte problemene i dette kapitlet, formulert med andre ord. Det er hele poenget med katalogen: noen få abstrakte ja/nei-spørsmål dukker opp igjen og igjen i praktiske kledninger, og når du kjenner den formelle formen, kjenner du dem igjen.

Alle åtte er skrevet som avgjørelsesproblemer — spørsmål med svaret ja eller nei. Det er ikke en tilfeldighet. Klassene $P$ og $NP$ er definert for ja/nei-spørsmål, så et optimeringsproblem («hva er den største klikken?») må først skrives om med en terskel $k$ («finnes det en klikk på minst $k$ noder?») før det i det hele tatt gir mening å spørre om det er i $NP$ .

Avgjørelsesform med terskel

k

NP-hardt

X

NP-komplett (NPC)

X

NPC-bevis i to deler

X

✏️Eksempel 1: Fra optimering til avgjørelse

Et transportselskap skal innom fem terminaler P, Q, R, S og T én gang hver og tilbake til utgangspunktet. Kostnadene mellom terminalene er:

P	Q	R	S	T
P	—	12	19	25	14
Q	12	—	10	21	17
R	19	10	—	11	23
S	25	21	11	—	13
T	14	17	23	13	—

a) Skriv om spørsmålet «hva er den billigste rundturen?» til et avgjørelsesproblem.
b) Hva er svaret på avgjørelsesspørsmålet for

k = 59

og for

k = 60

a) Avgjørelsesvarianten er: gitt kostnadene og et tall $k$ — finnes det en rundtur som besøker hver terminal nøyaktig én gang og ender der den startet, med samlet kostnad høyst $k$ ? Terskelen

k

er en del av inputen.

b) Med fem terminaler finnes det $(5-1)! = 24$ rundturer å sammenligne. Den billigste er

P - Q - R - S - T - P   med kostnad 12 + 10 + 11 + 13 + 14 = 60

$k = 59$ : nei. $k = 60$ : ja.

Legg merke til hva som skjedde: det opprinnelige spørsmålet hadde et tall som svar, avgjørelsesvarianten har ja eller nei. Det er den formen klassene $P$ og $NP$ er definert for, og derfor den formen alle de åtte problemene i dette kapitlet skrives på.

📝Oppgave 1

Eksamensnivå, sjanger D

Et sykehus vil vite hvor få vaktposter det holder å bemanne for at hver korridor skal ha bemanning i minst én av endene sine. Korridorene går mellom vaktposter.

a) Hvilket av katalogproblemene er dette?
b) Skriv problemet som et avgjørelsesproblem, med grafnotasjon.

CIRCUIT-SAT — der kjeden begynner (~12 min)

Alle de andre problemene i katalogen har fått NP-hardheten sin arvet fra et problem som allerede var kjent vanskelig. Men det første problemet kunne ikke arve noe — det fantes ingenting å arve fra. Det måtte bevises fra bunnen, direkte mot definisjonen av $NP$ .

Det problemet er CIRCUIT-SAT, og ideen bak beviset er verdt å kunne fortelle i tre setninger. Selve beviset er langt og teknisk, og det spørres det ikke om. Hovedideen spørres det om.

Boolsk kombinatorisk krets

n

CIRCUIT-SAT

C

📜Hovedideen: hvorfor CIRCUIT-SAT er NP-komplett

Påstanden: CIRCUIT-SAT er NP-komplett. Medlemskapet i

NP

er lett (evaluér kretsen på den foreslåtte inputen). Det interessante er hardheten, og den bevises ikke ved å redusere fra et annet NP-komplett problem — det fantes ikke noe å redusere fra.

Ideen i tre setninger. La $A$ være et hvilket som helst problem i $NP$ . Da finnes det per definisjon en verifikasjonsalgoritme $V$ som, gitt en instans $x$ og et sertifikat $y$ , svarer 1 eller 0 på polynomisk tid. En algoritme som kjører i polynomisk tid på en datamaskin, kan skrives om til en krets av polynomisk størrelse som regner ut det samme: maskinen er tross alt bygget av logiske porter, og et polynomisk antall regneskritt gir et polynomisk antall porter.

Konstruksjonen. For en gitt instans $x$ bygger vi kretsen som simulerer $V$ med $x$ fastspikret i portene, og lar sertifikatet $y$ være kretsens innganger. Da gjelder:

$x \text{ er en ja-instans av } A \iff \text{kretsen er oppfyllbar}$

For er $x$ en ja-instans, finnes et sertifikat som får $V$ til å svare 1, og nettopp den inputen gjør kretsen oppfyllbar. Og finnes en input som gjør kretsen oppfyllbar, er den inputen et sertifikat som får $V$ til å godta $x$ .

Konsekvensen. Dette er en polynomisk reduksjon $A \le_p$ CIRCUIT-SAT, og den fungerer for hvert $A \in NP$ . Altså er CIRCUIT-SAT NP-hardt, og siden det også ligger i $NP$ , er det NP-komplett.

Setningen du skal kunne skrive på eksamen: kretsen simulerer verifikasjonsalgoritmen, og sertifikatet er kretsens input — derfor er kretsen oppfyllbar nøyaktig når instansen har et gyldig sertifikat.

✏️Eksempel 2: Er kretsen oppfyllbar?

To små kretser:

C(a, b, c) = ((a AND NOT b) OR (b XOR c)) AND (NOT a OR c)
D(a, b)    = (a OR b) AND (NOT a) AND (NOT b)

Avgjør for hver av dem om den er oppfyllbar, og oppgi et sertifikat der svaret er ja.

Med tre innganger er det $2^3 = 8$ kombinasjoner å prøve for C:

C er oppfyllbar. Sertifikat: $a=0,\ b=0,\ c=1$ . Verifikasjonen er å sette inn de tre verdiene og evaluere de fire portene — det tar konstant tid her, og lineær tid i antall porter generelt.

For D er alle fire kombinasjonene 0:

D er ikke oppfyllbar. Merk asymmetrien: ja-svaret har et kort sertifikat som lar seg sjekke lynraskt, mens nei-svaret her krevde at vi gikk gjennom alle kombinasjonene. Det er nøyaktig denne asymmetrien definisjonen av $NP$ bygger på.

📝Oppgave 2

Eksamensnivå, sjanger G

Beviset for at CIRCUIT-SAT er NP-komplett skiller seg fra alle de andre NPC-bevisene i katalogen.

a) På hvilken måte skiller det seg?
b) Hva er sertifikatet i beviset, og hva er det kretsen simulerer?

Typiske feil: CIRCUIT-SAT-beviset

Felle #1 — reversert reduksjonsretning, altså å redusere fra sitt eget problem til et kjent vanskelig problem og tro at det beviser at ens eget problem er vanskelig. Den slår inn her i en egen variant: å tro at CIRCUIT-SAT-beviset reduserer fra CIRCUIT-SAT til noe annet, eller at det reduserer fra et annet NP-komplett problem. Ingen av delene. Beviset går fra et vilkårlig

A \in NP

til CIRCUIT-SAT.

To andre feil i samme område:

- Å hoppe over medlemskapet. «Vi reduserer fra CIRCUIT-SAT, altså er problemet NP-komplett» er et halvt bevis. Reduksjonen gir NP-hardhet; NP-kompletthet krever i tillegg at problemet ligger i $NP$ .
- Å blande sertifikat og løsning. Sertifikatet er forslaget som verifiseres, ikke svaret verifikatoren gir. I CIRCUIT-SAT er sertifikatet inputkombinasjonen, ikke bittet 1 på utgangen.

Reduksjonskjeden — slik arves hardheten videre (~14 min)

Når først ett problem er kjent NP-komplett, blir de neste billigere. Er $Y$ NP-komplett og du greier å vise $Y \le_p X$ , arver $X$ hardheten: alt i $NP$ reduseres til $Y$ , og $Y$ reduseres til $X$ , så alt i $NP$ reduseres til $X$ . Det er transitiviteten som gjør katalogen mulig.

Kjeden i pensum ser slik ut:

CIRCUIT-SAT -> SAT -> 3-CNF-SAT -> CLIQUE -> VERTEX-COVER -> HAM-CYCLE -> TSP
                      3-CNF-SAT -> SUBSET-SUM

Pilene peker fra det som allerede er kjent vanskelig, til det nye. Leser du en pil feil vei, har du snudd hele argumentet. Merk også at hver pil bare gir NP-hardhet videre: at hvert av problemene også ligger i $NP$ , må vises for seg, med sitt eget sertifikat.

Literal, klausul og konjunktiv normalform

x_2

SAT (formeloppfyllbarhet)

\varphi

3-CNF-SAT

\varphi

✏️Eksempel 3: Sertifikat og verifikasjon i 3-CNF-SAT

Gitt formelen

$\varphi = (x_1 \vee \neg x_2 \vee x_3) \wedge (\neg x_1 \vee x_2 \vee x_3) \wedge (\neg x_1 \vee \neg x_2 \vee \neg x_3) \wedge (x_1 \vee x_2 \vee \neg x_3)$

a) Er $\varphi$ på 3-CNF-form? Hvor mange klausuler og literaler har den?
b) Er $\varphi$ oppfyllbar? Oppgi i så fall et sertifikat, og vis hvordan verifikasjonen kjøres.

a) Ja. Fire klausuler, hver med nøyaktig tre literaler — til sammen 12 literaler, over tre variabler.

b) Ja, $\varphi$ er oppfyllbar. Med tre variabler finnes det åtte tilordninger, og fire av dem gjør formelen sann:

Sertifikat: $x_1 = 1,\ x_2 = 0,\ x_3 = 1$ . Verifikasjonen går klausul for klausul:

  klausul 1: (x1 OR NOT x2 OR x3)        x1 = 1        -> sann
  klausul 2: (NOT x1 OR x2 OR x3)        x3 = 1        -> sann
  klausul 3: (NOT x1 OR NOT x2 OR NOT x3) NOT x2 = 1   -> sann
  klausul 4: (x1 OR x2 OR NOT x3)        x1 = 1        -> sann

Alle fire klausulene er sanne, så verifikatoren svarer 1. Arbeidet er lineært i antall literaler, altså $\Theta(m)$ for $m$ literaler — og det er nettopp det som plasserer 3-CNF-SAT i $NP$ .

Legg merke til hva sertifikatet ikke er: det er ikke en oppskrift på å finne tilordningen. Å finne den er det vanskelige; å sjekke den er billig.

📝Oppgave 3

Eksamensnivå, sjanger D…

Gitt formelen

$\psi = (y_1 \vee y_2 \vee \neg y_3) \wedge (\neg y_1 \vee y_2 \vee y_3) \wedge (y_1 \vee \neg y_2 \vee y_3) \wedge (\neg y_1 \vee \neg y_2 \vee \neg y_3) \wedge (y_1 \vee y_2 \vee y_3)$

a) Hvor mange klausuler og literaler har $\psi$ , og er den på 3-CNF-form?
b) Oppgi ett sertifikat som viser at $\psi$ er en ja-instans av 3-CNF-SAT.
c) Hvor mange av de åtte mulige tilordningene gjør $\psi$ sann?

CLIQUE og VERTEX-COVER — de to som forveksles (~14 min)

Nå er vi tilbake ved panelet fra åpningen. De to neste problemene i kjeden handler begge om å velge ut noder i en graf, og de forveksles oftere enn noe annet par i katalogen. Forskjellen er verdt å skrive ned i klartekst før definisjonene kommer:

- CLIQUE ser på nodene innbyrdes: alle de valgte skal være naboer med hverandre. Du vil ha minst $k$ noder — jo flere, jo bedre.
- VERTEX-COVER ser på kantene: hver kant i hele grafen skal ha minst én ende blant de valgte. Du vil klare deg med høyst $k$ noder — jo færre, jo bedre.

Én av dem er et maksimeringsproblem med et krav på innsiden av utvalget, den andre er et minimeringsproblem med et krav på utsiden. Ulikhetstegnet peker derfor motsatt vei i de to definisjonene, og det er det aller lettest å bomme på.

Klikk (clique)

C \subseteq V

CLIQUE

G=(V,E)

Nodedekke (vertex cover)

C \subseteq V

VERTEX-COVER

G=(V,E)

Komplementgrafen

\bar{G} = (V, \bar{E})

✏️Eksempel 4: Samme graf, to spørsmål

En graf $G$ med seks noder:

  V = {a, b, c, d, e, f}
  E = {(a,b), (a,c), (b,c), (b,d), (c,d), (d,e), (d,f), (e,f)}

a) Er (G, k=3) en ja-instans av CLIQUE?
b) Er (G, k=3) en ja-instans av VERTEX-COVER?
c) Hva er svaret for VERTEX-COVER med $k = 4$ ?

a) Ja. Nodene {b, c, d} er parvis naboer: (b,c), (b,d) og (c,d) ligger alle i

E

. Det er en klikk på tre noder, og CLIQUE spør om minst

k

b) Nei. Grafen har åtte kanter, og ingen tre noder treffer alle. Det ser man raskest slik: kantene (a,b), (c,d) og (e,f) er parvis disjunkte — de deler ingen endepunkt. Et dekke må ha minst én node fra hver av dem, men da er alle tre brukt opp, og kanten (a,c) er fortsatt udekket med mindre en av de tre valgte er a eller c. Uttømmende gjennomgang bekrefter det: det finnes ingen nodedekker med tre noder.

c) Ja. {b, c, d, f} dekker alle åtte kantene:

  (a,b) -> b     (a,c) -> c     (b,c) -> b,c   (b,d) -> b,d
  (c,d) -> c,d   (d,e) -> d     (d,f) -> d,f   (e,f) -> f

Uttømmende gjennomgang av alle delmengder gir dette bildet:

$k$	antall klikker med $k$ noder	antall nodedekker med $k$ noder
1	6	0
2	8	0
3	3	0
4	0	7
5	0	6
6	0	1

Største klikk er altså 3, minste nodedekke er 4 — på samme graf. Det er den beste illustrasjonen av at de to problemene spør om helt forskjellige ting. Legg også merke til at

6 - 4 = 2

, og at største uavhengige mengde i

G

nettopp er 2 noder ({c, f}).

📜Pseudokode-kontrakt: `Verify-Clique`

1. Antagelser om representasjon. Grafen

G=(V,E)

er gitt som nabomatrise, slik at E[u][v] kan slås opp i konstant tid. Nodene er nummerert 1..n. Sertifikatet V' er en liste av nodenummer uten gjentakelser.

2. Pre- og postbetingelse. Før: k er et heltall mellom 0 og n, og V' er en liste av noder fra V. Etter: returverdien er 1 hvis og bare hvis V' er en klikk i $G$ med minst k noder. Grafen endres ikke.

3. Pseudokoden.

Verify-Clique(G, k, V')
  Input:  graf G = (V, E) som nabomatrise, terskel k, sertifikat V'
  Output: 1 hvis V' er en klikk i G med minst k noder, ellers 0
  if length(V') < k
      return 0
  for hver node u i V'
      if u ikke i V
          return 0
  for hver node u i V'
      for hver node v i V' med v != u
          if E[u][v] = 0
              return 0
  return 1

4. Grunnideen. Verifikatoren gjør ingen søking. Den tar imot et ferdig forslag og sjekker de to kravene i definisjonen av CLIQUE hver for seg: at utvalget er stort nok, og at hvert par i utvalget er en kant.

5. Kjøretid. Den doble løkken går over høyst $\lvert V' \rvert^2 \le n^2$ par, og hvert oppslag i nabomatrisen tar konstant tid, altså $O(n^2)$ — polynomisk i inputstørrelsen. Det er nettopp dette som viser at CLIQUE $\in NP$ .

📝Oppgave 4

Eksamensnivå, sjanger C

Gitt grafen

  V = {p, q, r, s, t, u}
  E = {(p,q), (p,r), (p,u), (q,r), (q,t), (r,s), (s,t), (t,u)}

a) Oppgi størrelsen på den største klikken, og hvilke noder den består av.
b) Oppgi størrelsen på det minste nodedekket, og hvilke noder det består av.
c) Er (G, k=3) en ja-instans av CLIQUE? Av VERTEX-COVER?

📝Oppgave 5

Eksamensnivå, sjanger D

a) Definér CLIQUE og VERTEX-COVER som avgjørelsesproblemer, med grafnotasjon.
b) Pek ut de to stedene definisjonene skiller lag.
c) En klikk på

k

noder i komplementgrafen

\bar{G}

svarer til hva i

G

Typiske feil: CLIQUE mot VERTEX-COVER

Dette paret står for flere tapte poeng enn noe annet i katalogen. Tre konkrete feil:

- Snudd ulikhetstegn. Å skrive «finnes det et nodedekke med minst $k$ noder?» gjør spørsmålet trivielt — hele $V$ er alltid et dekke. Et definisjonssvar med feil ulikhetstegn er galt, ikke omtrentlig riktig.
- Krav på feil objekt. «Et nodedekke er en mengde noder som er parvis naboer» er definisjonen av en klikk. Nodedekket stiller krav til kantene.
- Å tro at største klikk og minste nodedekke henger sammen på samme graf. De gjør det ikke. Sammenhengen går via komplementgrafen: klikk i $\bar{G}$ svarer til uavhengig mengde i $G$ , som svarer til komplementet av et nodedekke i $G$ . På grafen i Eksempel 4 var største klikk 3 og minste nodedekke 4, uten noen sammenheng mellom tallene.

HAM-CYCLE, TSP og SUBSET-SUM (~10 min)

De tre siste i katalogen. To av dem handler om rundturer og henger tett sammen; den tredje handler om tall, og den skal du være ekstra våken på — den er kilden til den vanligste sammenblandingen i hele Del 7.

Hamiltonsk sykel

G=(V,E)

HAM-CYCLE

G=(V,E)

TSP (handelsreisendes problem)

G=(V,E)

SUBSET-SUM

S = \{s_1, \dots, s_n\}

Typiske feil: pseudopolynomisk mot NP-hardt

Felle #7 — å blande pseudopolynomisk og NP-hardt. Den utløses nesten alltid av SUBSET-SUM eller 0-1-ryggsekk, og den går slik: «Det finnes en algoritme som er

\Theta(nt)

, altså er problemet i

P

, altså er det ikke NP-hardt.» Det er galt, og feilen sitter i hva

t

er.

Kjøretiden til en algoritme måles i lengden av inputen i bit. Et måltall $t$ skrives med $\lceil \lg t \rceil$ bit. Er $t = 10^9$ , tar tallet 30 bit å skrive ned, men tabellen har en milliard kolonner. Kjøretiden er altså eksponentiell i inputlengden, selv om uttrykket $\Theta(nt)$ ser polynomisk ut.

En algoritme som er polynomisk i tallenes verdi, men eksponentiell i tallenes lengde, kalles pseudopolynomisk. Den er nyttig når tallene er små, og den motbeviser ingenting om NP-hardhet. Samme resonnement gjelder Ford-Fulkerson: den er pseudopolynomisk fordi kjøretiden avhenger av kapasitetenes størrelse, og det gjør ikke maks-flyt til et vanskelig problem.

✏️Eksempel 5: To eksamenssvar i kortsvarsform

a) Definér SUBSET-SUM, og avgjør om

S = \{3, 8, 11, 17, 22\}

med

t = 30

er en ja-instans.
b) En reduksjon 3-CNF-SAT

\le_p

CLIQUE er gitt. Hva beviser den, og hva beviser den ikke?

a) Gitt en mengde positive heltall

S

og et måltall

t

: finnes det en delmengde av

S

som summerer seg til nøyaktig

t

Ja-instans. Sertifikat: $\{8, 22\}$ , siden $8 + 22 = 30$ . Verifikasjonen er én summering.

Til sammenligning er $t = 21$ en nei-instans for samme $S$ : ingen delmengde treffer 21 nøyaktig.

b) Retningen er fra 3-CNF-SAT til CLIQUE. Siden 3-CNF-SAT er NP-komplett, beviser reduksjonen at CLIQUE er NP-hardt — CLIQUE er minst like vanskelig som 3-CNF-SAT.

Den beviser ikke at CLIQUE er NP-komplett: til det trengs i tillegg at CLIQUE ligger i $NP$ , som vises separat med nodemengden som sertifikat. Og den sier ingenting om at 3-CNF-SAT skulle være lett — en reduksjon oppover i vanskelighet forteller ingenting om kilden.

Legg merke til lengden på svarene. Deloppgave a) er én setning pluss ett sertifikat; b) er tre linjer. Det er den formen fasitene bruker, og mer tekst gir ikke mer uttelling.

📝Oppgave 6

Eksamensnivå, sjanger D…

a) Definér HAM-CYCLE og TSP som avgjørelsesproblemer.
b) Hvorfor trenger TSP et tall

k

i inputen, mens HAM-CYCLE ikke gjør det?
c) Grafen

H

har nodene {A, B, C, D, E} og kantene (A,B), (B,C), (C,D), (D,E), (A,C), (B,D). Er

H

en ja-instans av HAM-CYCLE?

📝Oppgave 7

Eksamensnivå, sjanger F

En student skriver: «SUBSET-SUM kan løses med en tabell i $\Theta(nt)$ tid, der $n$ er antall tall og $t$ er måltallet. $\Theta(nt)$ er et polynom, altså er SUBSET-SUM i $P$ .»

a) Stemmer konklusjonen?
b) Hva heter fenomenet, og hvor sitter feilen presist?

📝Oppgave 8

Eksamensnivå, sjanger G

For å vise at TSP er NP-hardt brukes denne konstruksjonen: ta en graf $G=(V,E)$ , bygg en komplett graf på de samme nodene, gi kostnad 0 til kantene som finnes i $E$ og kostnad 1 til de øvrige, og spør om det finnes en rundtur med kostnad høyst 0.

a) Hvilken vei går reduksjonen? Skriv den med $\le_p$ -notasjon.
b) Hvorfor er konstruksjonen svarbevarende begge veier?
c) Hva ville det ha bevist hvis noen i stedet hadde vist TSP $\le_p$ HAM-CYCLE?

📝Oppgave 9

Eksamensnivå, sjanger D…

En festivalsjef skal sette sammen et kveldsprogram. Hun har en liste over artister, og for hvert par vet hun om de har sagt ja til å opptre samme kveld. Hun vil vite om det finnes et program med minst åtte artister der alle har sagt ja til alle de andre.

Samtidig skal teknisk sjef bemanne lydsjekkene. Hver kabelstrekk mellom to scener må ha en tekniker i minst én av endene, og han vil vite om fem teknikere holder.

a) Hvilket katalogproblem er hvert av de to spørsmålene?
b) Skriv begge formelt, med den grafen du velger å bygge.
c) Festivalsjefen sier: «Siden jeg klarte å oversette mitt problem til CLIQUE, må mitt problem være NP-komplett.» Er det et gyldig argument?

Katalogen samlet (~4 min)

Alle åtte, med input, ja/nei-spørsmål, sertifikat og hvor hardheten kommer fra. Dette er kapitlets puggeflate — eksamen er hjelpemiddelfri, så tabellen skal sitte i hodet, ikke i en perm.

Problem	Input	Ja-spørsmålet	Sertifikat	Hardhet arvet fra
CIRCUIT-SAT	boolsk krets $C$	finnes en input som gir 1 ut?	inputkombinasjonen	ingen — bevist direkte mot definisjonen av $NP$
SAT	boolsk formel $\varphi$	finnes en tilordning som gjør $\varphi$ sann?	tilordningen	CIRCUIT-SAT
3-CNF-SAT	CNF-formel, tre literaler per klausul	finnes en tilordning som gjør $\varphi$ sann?	tilordningen	SAT
CLIQUE	graf $G$ , tall $k$	finnes $C$ med $\lvert C \rvert \ge k$ der alle er parvis naboer?	nodemengden $C$	3-CNF-SAT
VERTEX-COVER	graf $G$ , tall $k$	finnes $C$ med $\lvert C \rvert \le k$ som treffer hver kant?	nodemengden $C$	CLIQUE
HAM-CYCLE	graf $G$	finnes en sykel innom hver node nøyaktig én gang?	rekkefølgen	VERTEX-COVER
TSP	komplett graf med kostnader, tall $k$	finnes en rundtur med kostnad høyst $k$ ?	rekkefølgen	HAM-CYCLE
SUBSET-SUM	tallmengde $S$ , måltall $t$	finnes en delmengde med sum nøyaktig $t$ ?	delmengden	3-CNF-SAT

Verifikasjonstidene er alle polynomiske:

\Theta(n)

for de tre nederste,

O(n^2)

for de to grafproblemene i midten, og lineært i antall porter eller literaler for de tre øverste. Det er den ene halvparten av hvert NPC-bevis. Den andre halvparten er kolonnen helt til høyre.

Begrepsbank (~4 min)

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

Uavhengig mengde (independent set)

I \subseteq V

Reduksjonskjeden i pensum

NP

Det første NP-komplette problemet

NP

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.

P	Q	R	S	T
P	—	12	19	25	14
Q	12	—	10	21	17
R	19	10	—	11	23
S	25	21	11	—	13
T	14	17	23	13	—

P	Q	R	S	T
P	—	12	19	25	14
Q	12	—	10	21	17
R	19	10	—	11	23
S	25	21	11	—	13
T	14	17	23	13	—

P	Q	R	S	T
P	—	12	19	25	14
Q	12	—	10	21	17
R	19	10	—	11	23
S	25	21	11	—	13
T	14	17	23	13	—