7.4 DRILL — Reduksjonsretning og NP-argumenter

Full drill på sjanger G med fokus på det dokumenterte skillepunktet: hvilken vei reduserer du, og hva beviser det.

85 min

13 oppgaver

DRILLReduksjonsretningNP-argumenter

Din fremgang i kapitlet

0 / 13 oppgaver

Kapitlets plass i kurset

Bygger på

7.3NP-komplette problemer

Brukes videre i

7.PPrøver til del 7: NP-kompletthet og reduksjoner 8.2DRILL — Åpen algoritmedesign via reduksjon

Dette er kapitlet som avgjør flest poeng per side i hele boka.

- Sjanger G — reduksjon og NP-argument, altså at du oppgir hvilken vei reduksjonen går, hva den beviser og hva den ikke beviser, er til stede i 100 % (17 av de 17 settene i grunnlaget). Sjanger F — ja/nei-vurdering av et utsagn, med ja eller nei først og deretter én presis setning — kommer i tillegg.
- Dette kapitlet har høyeste prioritet — dette må sitte.

Reduksjonsretningen er det enkeltpunktet løsningsforslagene oftest fremhever som skillet mellom riktig og galt svar. En besvarelse som reduserer feil vei, får ikke delvis uttelling for å ha nevnt de riktige problemene — argumentet beviser da bokstavelig talt ingenting om problemet det handler om.

Kapitlet er en treningsbank: det er ingen ny teori her, bare en oppskrift, én gjennomarbeidet case og tretten oppgaver på eksamensnivå. Regn 85 minutter, og del det gjerne på to økter — det er lagt inn pausepunkter underveis.

Forkunnskaper

Kapitlet bygger på kap. 7.1, kap. 7.2 og kap. 7.3. Fire resultater derfra brukes i hver eneste oppgave under, og de står her ferdig oppfrisket:

1. $NP$ handler om verifikasjon. Et problem er i $NP$ hvis hvert ja-svar har et sertifikat — et forslag til løsning — som en verifikasjonsalgoritme godkjenner i polynomisk tid.
2. Retningsregelen. $A \le_p B$ betyr at $A$ reduseres til $B$ , og at $B$ er minst like vanskelig som $A$ . For å vise at et problem $X$ er vanskelig, reduserer du fra noe kjent vanskelig til $X$ .
3. NP-hardt mot NP-komplett. NP-hardt betyr at alt i $NP$ reduseres til problemet. NP-komplett betyr NP-hardt og i $NP$ — to ledd, ikke ett.
4. Katalogen. De åtte navngitte NP-komplette problemene er CIRCUIT-SAT, SAT, 3-CNF-SAT, CLIQUE, VERTEX-COVER, HAM-CYCLE, TSP og SUBSET-SUM. Kjenner du ikke den formelle definisjonen av dem, kan du ikke bruke dem som utgangspunkt for en reduksjon — repeter kap. 7.3 først.

Fra kap. 5.2 og kap. 6.2 hentes to fakta som brukes i oppgavene: Ford-Fulkerson er pseudopolynomisk, og 0-1-Knapsack løses i $\Theta(nm)$ der $m$ er ryggsekkens kapasitet — en tallverdi, ikke en inputlengde.

Notasjons- og pseudokodeliste

Fem steg som avgjør hvert NP-spørsmål (~15 min)

Alle NP-oppgaver i faget kan besvares med den samme oppskriften. Den er kort med vilje: eksamen har rundt 20 likt vektede oppgaver på fire timer, og du har ikke tid til å tenke deg fram til strukturen hver gang.

📜Løsningsoppskriften for NP-spørsmål

1. Hva slags påstand er det? Les oppgaven og avgjør hvilket av tre spørsmål som faktisk stilles: er $X$ i $NP$ ?, er $X$ NP-hardt?, eller er $X$ NP-komplett? De tre har helt forskjellige svar, og den vanligste tapte poengen er å svare på et annet enn det som ble spurt om.

2. Skal du vise vanskelighet (NP-hardt), reduserer du FRA et kjent NP-komplett problem TIL $X$ . Aldri motsatt. Velg det katalogproblemet som ligner mest i form — tallmengder mot SUBSET-SUM, nodeutvalg mot CLIQUE eller VERTEX-COVER, rundturer mot HAM-CYCLE. Skriv retningen eksplisitt som $Y \le_p X$ , og les den høyt: jeg reduserer fra det kjente vanskelige til mitt problem, altså er mitt problem minst like vanskelig. Reduksjonen må oppfylle tre krav: den må kjøre i polynomisk tid, den må gi en lovlig $X$ -instans, og den må bevare svaret begge veier — ja gir ja, og nei gir nei.

3. Skal du vise medlemskap i $NP$ , oppgir du et sertifikat og en polynomisk verifikasjon. Si konkret hva sertifikatet er (en nodemengde, en tilordning, en rekkefølge, en delmengde), hva verifikasjonsalgoritmen sjekker, og hvor lang tid den bruker. To linjer holder.

4. Skal du si noe om konsekvensen, går den via $P = NP$ . En polynomisk algoritme for ett NP-komplett problem gir polynomiske algoritmer for alle problemer i $NP$ , altså $P = NP$ . Motsatt vei: er $X \le_p Y$ og $Y \in P$ , så er $X \in P$ .

5. Skill pseudopolynomisk fra NP-hardt. En kjøretid som $\Theta(nt)$ eller $\Theta(nm)$ , der $t$ eller $m$ er en tallverdi i inputen og ikke en lengde, er pseudopolynomisk. Den gjør ikke problemet polynomisk løsbart, og den motbeviser ingen NP-hardhet.

Og alltid, til slutt: skriv én setning om hva argumentet ikke beviser. Det er halve poenget i sjanger G, og det er den setningen som viser at du har forstått retningen og ikke bare pugget den.

Typiske feil i NP-argumenter

Fire feil står for nesten alle tapte poeng i sjanger G. De er verdt å kunne kjenne igjen på et halvt sekund.

- 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. Å vise $X \le_p$ TSP forteller bare at $X$ ikke er vanskeligere enn TSP. Det er ikke et delvis riktig svar; det er et svar på et annet spørsmål.
- Å forveksle «i $NP$ » med «NP-hardt». «Problemet er i $NP$ , altså er det vanskelig» er galt: alt i $P$ ligger også i $NP$ , og sortering er ikke vanskelig. Medlemskap sier at ja-svar er lette å sjekke.
- Å stoppe etter én av de to delene. Reduksjonen alene gir NP-hardhet. Sertifikatet alene gir medlemskap. NP-kompletthet krever begge.
- Felle #7 — å blande pseudopolynomisk og NP-hardt. «Ryggsekk løses i $\Theta(nm)$ , altså er det ikke NP-hardt» er galt fordi $m$ er en tallverdi. Og motsatt: at Ford-Fulkerson er pseudopolynomisk, gjør ikke maks-flyt vanskelig — maks-flyt løses i polynomisk tid av Edmonds-Karp i $O(VE^2)$ .

Gjennomarbeidet case med margnotater (~20 min)

Et idrettslag har fått en bunke regninger etter en sesong og vil vite om utgiftene kan deles i to like store deler, slik at de to eierklubbene betaler nøyaktig like mye hver. Ingen regning kan splittes.

Det spørsmålet har et navn i katalogspråket. Vi kaller problemet LIKDELING: gitt en endelig mengde positive heltall $S$ — kan $S$ deles i to disjunkte delmengder med nøyaktig lik sum?

Oppgaven er den typiske: vis at LIKDELING er NP-komplett. Under er hele svaret, med margnotater om hvorfor hvert steg står der det står, og hvor delpoengene ligger.

✏️Eksempel 1: LIKDELING er NP-komplett

LIKDELING. Gitt en endelig mengde positive heltall

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

— finnes det en delmengde

S' \subseteq S

slik at

$\sum_{s \in S'} s = \sum_{s \in S \setminus S'} s\ ?$

Vis at LIKDELING er NP-komplett.

Steg 1 — hva slags påstand er dette?

«NP-komplett» er to påstander i én: LIKDELING $\in NP$ , og LIKDELING er NP-hardt. Svaret må derfor ha to atskilte deler.

Margnotat: å skrive «to deler» først koster én linje og sikrer at du ikke glemmer den ene. En besvarelse som bare gir reduksjonen, har vist NP-hardhet — ikke NP-kompletthet.

---

Steg 2 — del 1: medlemskap i $NP$ .

Sertifikatet er delmengden $S'$ selv. Verifikasjonsalgoritmen summerer $S'$ , summerer resten, og sammenligner de to tallene. Det er $\Theta(n)$ addisjoner på tall som allerede står i inputen, altså polynomisk i inputlengden. Altså LIKDELING $\in NP$ .

Margnotat: to linjer er nok, men de to linjene må være der. Fasitene krever at sertifikatet navngis konkret — «en delmengde» — og at verifikasjonstiden oppgis.

---

Steg 3 — del 2: velg problem og retning.

Vi velger SUBSET-SUM, som er kjent NP-komplett og har samme form: tallmengder og summer. Retningen er

$\text{SUBSET-SUM} \le_p \text{LIKDELING}$

Lest høyt: jeg reduserer fra SUBSET-SUM, som jeg vet er vanskelig, til LIKDELING, altså er LIKDELING minst like vanskelig som SUBSET-SUM.

Margnotat: skriv pilen med $\le_p$ og skriv setningen. Det er nettopp her feil retning gir null uttelling, og det er også her en riktig retning sikrer poenget selv om konstruksjonen skulle halte.

---

Steg 4 — konstruksjonen.

La $(S, t)$ være en vilkårlig SUBSET-SUM-instans, og la $\sigma = \sum_{s \in S} s$ . Vi bygger LIKDELING-instansen

$S' = S \cup \{\,2\sigma - t,\ \sigma + t\,\}$

Summen av $S'$ er $\sigma + (2\sigma - t) + (\sigma + t) = 4\sigma$ , så en likdeling må gi $2\sigma$ i hver halvdel.

Polynomisk tid: vi legger til to tall, hvert på høyst $\lceil \lg (2\sigma) \rceil + 1$ bit, og $\sigma$ er summen av tall som allerede står i inputen. Konstruksjonen er $\Theta(n)$ addisjoner.

Ja gir ja: finnes $A \subseteq S$ med sum $t$ , så har $A \cup \{2\sigma - t\}$ summen $t + 2\sigma - t = 2\sigma$ , og resten har summen $(\sigma - t) + (\sigma + t) = 2\sigma$ . Altså er $S'$ en ja-instans.

Nei gir nei (vist kontrapositivt): anta at $S'$ kan deles i to halvdeler à $2\sigma$ . De to nye tallene kan ikke ligge i samme halvdel, for $(2\sigma - t) + (\sigma + t) = 3\sigma > 2\sigma$ . Se på halvdelen som inneholder $2\sigma - t$ : resten av den halvdelen er en delmengde av $S$ med sum $2\sigma - (2\sigma - t) = t$ . Altså er $(S, t)$ en ja-instans av SUBSET-SUM.

Margnotat: begge retninger må stå. En reduksjon som bare viser «ja gir ja» er ikke svarbevarende — den kan gjøre nei-instanser om til ja-instanser, og da beviser den ingenting.

---

Kontroll på tall. Med $S = \{4, 7, 9, 12\}$ og $t = 13$ er $\sigma = 32$ , og de to nye tallene blir $2\sigma - t = 51$ og $\sigma + t = 45$ :

  SUBSET-SUM:  S = {4, 7, 9, 12},  t = 13   ->  JA, delmengden {4, 9}
  LIKDELING:   S' = {4, 7, 9, 12, 51, 45},  sum = 128, halvparten = 64
               deling: {4, 9, 51} = 64   og   {7, 12, 45} = 64   ->  JA

  SUBSET-SUM:  S = {4, 7, 9, 12},  t = 14   ->  NEI
  LIKDELING:   S' = {4, 7, 9, 12, 50, 46},  sum = 128, halvparten = 64
               ingen deling gir 64 og 64                        ->  NEI

---

Steg 5 — konklusjon, og hva argumentet ikke beviser.

LIKDELING er i $NP$ og NP-hardt, altså NP-komplett.

Argumentet beviser ikke at LIKDELING er uløselig i praksis: det finnes en tabellalgoritme i $\Theta(n\sigma)$ tid, akkurat som for SUBSET-SUM. Den er pseudopolynomisk, siden $\sigma$ er en tallverdi og ikke en inputlengde, og den motsier derfor ikke NP-hardheten.

Det beviser heller ikke noe om at SUBSET-SUM skulle være lett. Reduksjonen går oppover i vanskelighet, og sier ingenting om kilden.

Margnotat: siste avsnitt er ofte det som skiller et fullt svar fra et halvt. Sjanger G ber alltid om både hva reduksjonen beviser og hva den ikke beviser.

📜Pseudokode-kontrakt: `Verify-Likdeling`

1. Antagelser om representasjon. Tallmengden er gitt som et array S[1..n] av positive heltall, indeks fra 1. Sertifikatet S' er gitt som et array valg[1..n] av 0 og 1, der valg[i] = 1 betyr at S[i] havner i den første halvdelen.

2. Pre- og postbetingelse. Før: S er ikke tom, og valg har samme lengde som S. Etter: returverdien er 1 hvis og bare hvis de to halvdelene valg beskriver, har nøyaktig lik sum. S og valg endres ikke.

3. Pseudokoden.

Verify-Likdeling(S, valg)
  Input:  array S[1..n] av positive heltall, array valg[1..n] med 0/1
  Output: 1 hvis de to delene har lik sum, ellers 0
  venstre = 0
  hoyre = 0
  for i = 1 to n
      if valg[i] = 1
          venstre = venstre + S[i]
      else
          hoyre = hoyre + S[i]
  if venstre = hoyre
      return 1
  return 0

4. Invarianten. Etter iterasjon $j$ er venstre summen av de valgte tallene blant S[1..j], og hoyre summen av de øvrige blant S[1..j]. Ved $j = n$ er de to tallene summene av de to halvdelene.

5. Kjøretid. Én gjennomgang av arrayet med konstant arbeid per element gir $\Theta(n)$ addisjoner — polynomisk i inputlengden. Det er nøyaktig dette som viser at LIKDELING $\in NP$ .

— naturlig pausepunkt —

Oppskriften og casen er kjernestoffet. Resten av kapitlet er trening, og den tåler å bli tatt i en egen økt. Før du går videre: lukk boka og skriv ned de fem stegene og retningsregelen fra hukommelsen. Får du dem ned, er du klar for oppgavene.

Hvilken vei, og hva beviser den (~25 min)

Åtte oppgaver som trener steg 1 til 4 i oppskriften. Skriv svaret ferdig før du åpner fasiten — det er den korte, presise formuleringen som trenes her, ikke gjenkjennelsen.

📝Oppgave 1

Eksamensnivå, sjanger G

Du skal vise at problemet PANELVALG er NP-hardt. PANELVALG spør, gitt en liste over fagpersoner, en oversikt over hvilke par som kan sitte sammen, og et tall $k$ : finnes det et panel på minst $k$ personer der alle par kan sitte sammen? Du har CLIQUE tilgjengelig som kjent NP-komplett problem.

a) Skriv reduksjonen med $\le_p$ -notasjon, i riktig retning.
b) Beskriv konstruksjonen i én setning.
c) Hva beviser reduksjonen, og hva beviser den ikke?

📝Oppgave 2

Eksamensnivå, sjanger F

Avgjør for hvert utsagn om det er sant eller usant.

a) Alle problemer i $NP$ er NP-komplette.
b) $P \subseteq NP$ .
c) Et problem i $NP$ kan ikke løses i polynomisk tid.
d) Finner noen en polynomisk algoritme for VERTEX-COVER, følger $P = NP$ .
e) Et NP-hardt problem må selv ligge i $NP$ .

Utsagnene c) og e) er de to varslene i denne oppgaven. c) fanger den klassiske definisjonsfeilen — å lese $NP$ som «ikke-polynomisk» i stedet for «verifiserbar i polynomisk tid». e) fanger skillet NP-hardt mot NP-komplett, som eksamen spør om i nesten hver termin.

Svarformen er verdt å merke seg: sant eller usant først, deretter én setning. Ikke to avsnitt. Ja/nei-oppgaver er blant de raskeste poengene i settet, og de er lette å ødelegge ved å skrive for mye.

📝Oppgave 3

Eksamensnivå, sjanger G

En student har vist at hennes problem KRETSPLAN reduseres polynomisk til 3-CNF-SAT, altså KRETSPLAN $\le_p$ 3-CNF-SAT.

a) Hva forteller det om vanskeligheten til KRETSPLAN?
b) Hva forteller det ikke?
c) Er det noe nyttig i det hele tatt hun kan konkludere med?

📝Oppgave 4

Eksamensnivå, sjanger G

Problemet SPORPLAN: gitt et jernbanenett med $n$ stasjoner, en liste over hvilke stasjonspar som er direkte forbundet, og et tall $k$ — finnes det en inspeksjonsrunde som starter og ender på samme stasjon og besøker hver stasjon nøyaktig én gang, med høyst $k$ direkteforbindelser i bruk?

a) Vis at SPORPLAN $\in NP$ . Oppgi sertifikat, hva verifikatoren sjekker, og kjøretiden.
b) Hvilket katalogproblem ville du redusert fra for å vise at SPORPLAN er NP-hardt, og i hvilken retning?

— naturlig pausepunkt —

Fire oppgaver unnagjort. De neste fire trener konsekvensledd og skillet mot pseudopolynomiske kjøretider — den andre halvparten av det eksamen spør om i dette temaet.

📝Oppgave 5

Eksamensnivå, sjanger F

0-1-Knapsack løses med dynamisk programmering i $\Theta(nm)$ tid, der $n$ er antall gjenstander og $m$ er ryggsekkens kapasitet.

a) Er $\Theta(nm)$ en polynomisk kjøretid for dette problemet?
b) Følger det at 0-1-ryggsekk er i $P$ ?
c) Hva heter kjøretidsklassen presist?

Oppgaven tester felle #7 i sin reneste form. Den kommer igjen i tre forkledninger på eksamen: 0-1-ryggsekk med kapasitet $m$ , SUBSET-SUM med måltall $t$ , og Ford-Fulkerson med kapasiteter. Alle tre har samme svar: kjøretiden er polynomisk i en tallverdi, ikke i inputens lengde.

Vær presis på hva du ikke påstår. Ford-Fulkerson er pseudopolynomisk, men maks-flyt er ikke et vanskelig problem — Edmonds-Karp løser det i $O(VE^2)$ , som er polynomisk. Å bruke pseudopolynomisk kjøretid som argument for at et problem er NP-hardt, er en av de tydeligste feilene et svar kan inneholde.

📝Oppgave 6

Eksamensnivå, sjanger F…

En student skriver: «Ford-Fulkerson er pseudopolynomisk. Altså er maks-flyt-problemet NP-hardt.»

a) Stemmer konklusjonen?
b) Hvor sitter feilen presist?
c) Hva er den korrekte statusen til maks-flyt?

📝Oppgave 7

Eksamensnivå, sjanger G

Anta at noen i morgen publiserer en algoritme som løser VERTEX-COVER i $O(n^7)$ tid.

a) Hva følger for TSP?
b) Hva følger for problemet «finnes det en sti fra $s$ til $t$ i en graf?»
c) Formulér konsekvensen i én setning.

📝Oppgave 8

Eksamensnivå, sjanger G

Problemet DELESTASJON: gitt en mengde positive heltall $S$ og et tall $t$ — finnes det en delmengde av $S$ med sum minst $t$ og høyst $t$ ?

a) Hvilket katalogproblem er dette i forkledning?
b) Skriv reduksjonen med $\le_p$ -notasjon og forklar hvorfor konstruksjonen er polynomisk.
c) Én student svarer: «Jeg reduserte DELESTASJON til SUBSET-SUM, altså er DELESTASJON NP-komplett.» Hva mangler i argumentet?

Er argumentet gyldig? (~25 min)

De fem siste oppgavene har samme form: et ferdig NPC-argument står der, og du skal avgjøre om det holder. Noen av dem gjør det. Feilene i de øvrige er små — de sitter i ett ledd, ikke i hele resonnementet, og det er nettopp slik de kommer på eksamen.

Les hvert argument mot de tre kravene til en gyldig reduksjon: polynomisk tid, lovlig instans ut, og svarbevaring begge veier. Og mot de to delene et NPC-bevis alltid har.

📝Oppgave 9

Eksamensnivå, sjanger G

Problemet BRETTDEKNING: gitt et rutebrett bestående av $t$ ruter på rekke, og en liste med brikkelengder $s_1, \dots, s_n$ — kan noen av brikkene legges etter hverandre slik at de dekker brettet nøyaktig, uten overlapp og uten hull? Brettet er gitt som en tegning, rute for rute.

En student argumenterer:

«Jeg reduserer FRA SUBSET-SUM TIL BRETTDEKNING. Gitt en SUBSET-SUM-instans $(S, t)$ tegner jeg opp et brett med $t$ ruter og lager én brikke av lengde $s_i$ for hvert tall $s_i$ i $S$ . En delmengde med sum $t$ finnes hvis og bare hvis brikkene kan dekke brettet nøyaktig. Retningen er riktig — fra det kjente vanskelige til mitt problem — så BRETTDEKNING er NP-hardt.»

Er argumentet gyldig?

Oppgaven trener den vanskeligste varianten av sjanger G: et argument der retningen er riktig, og der svarbevaringen også er riktig. De to tingene de fleste sjekker, er i orden — og likevel er argumentet ugyldig.

Lærdommen er å bruke alle tre kravene hver gang: polynomisk tid, lovlig instans ut, svarbevaring begge veier. Kravet om polynomisk tid gjelder konstruksjonen, og det brytes nesten alltid på samme måte: et tall i inputen skrives ut ledd for ledd i outputen. Kjenner du igjen det mønsteret, har du en sjekk som virker på alle slike oppgaver.

📝Oppgave 10

Eksamensnivå, sjanger G

2-CNF-SAT er samme problem som 3-CNF-SAT, bortsett fra at hver klausul har nøyaktig to literaler i stedet for tre.

En student argumenterer:

«2-CNF-SAT er et spesialtilfelle av SAT, og SAT er NP-komplett. Enhver 2-CNF-formel er jo også en helt vanlig boolsk formel, så jeg kan levere den rett inn i SAT. Altså er 2-CNF-SAT NP-komplett.»

a) Er argumentet gyldig?
b) Hvilken reduksjon har studenten faktisk beskrevet, og hva beviser den?

📝Oppgave 11

Eksamensnivå, sjanger G

En student skal vise at problemet BALANSE er NP-komplett, og skriver:

«Jeg har vist to reduksjoner: BALANSE $\le_p$ 3-CNF-SAT og 3-CNF-SAT $\le_p$ BALANSE. Begge kjører i polynomisk tid og bevarer svaret begge veier. Altså er BALANSE NP-komplett.»

a) Er argumentet gyldig?
b) Begrunn ledd for ledd hvilken av de to reduksjonene som gjør hvilken jobb.

Denne oppgaven er en motvekt. Etter tre oppgaver med feil i, er det fristende å svare «nei, feil retning» refleksmessig. Argumentet her er korrekt, og det testes om du kan si hvorfor — altså koble hver reduksjon til den delen av beviset den leverer.

Sjekklisten som virker: (1) er retningen på hardhetsreduksjonen fra det kjente vanskelige til det nye problemet? (2) er medlemskapet i $NP$ etablert, enten via et sertifikat eller via en reduksjon til noe som allerede er i $NP$ ? Er begge på plass, er argumentet gyldig — uansett hvor uvant det ser ut.

📝Oppgave 12

Eksamensnivå, sjanger G

Problemet TSP-EKSAKT: gitt en komplett graf med heltallige kantkostnader og et tall $k$ — er kostnaden til den billigste rundturen nøyaktig lik $k$ ?

En student skriver:

«Jeg reduserer FRA HAM-CYCLE TIL TSP-EKSAKT, i riktig retning og i polynomisk tid, og konstruksjonen bevarer svaret begge veier. Altså er TSP-EKSAKT NP-komplett.»

a) Er argumentet gyldig?
b) Hva er den sterkeste konklusjonen argumentet faktisk gir?

📝Oppgave 13

Eksamensnivå, sjanger G

Problemet VAKTPOSTER: en fabrikk har $n$ kryss og et sett med korridorer mellom kryssene. Ledelsen vil vite om det holder å bemanne $k$ kryss for at hver korridor skal ha bemanning i minst ett av kryssene sine.

Skriv et fullstendig argument for at VAKTPOSTER er NP-komplett. Ta med begge delene, konstruksjonen, svarbevaringen begge veier, kjøretiden på reduksjonen, og én setning om hva argumentet ikke beviser.

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.

Retningsregelen

A \le_p B

De tre kravene til en gyldig reduksjon

t

Medlemskapsdelen — sertifikat og verifikasjon

NP

NP-hardt mot NP-komplett i praksis

NP

Hva en reduksjon ikke beviser

NP

Kontrapositiv bruk av en reduksjon

X \le_p Y

P=NP-konsekvensen

X

Pseudopolynomisk

\Theta(nt)

Unær utskriving — reduksjonens usynlige feil

t

Spesialtilfelle-fellen

\le_p

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.