Begreper & referanser
Alle nøkkelbegrepene, formlene og referansene fra Problemer, instanser og reduksjoner, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.
Begreper
Sentrale begreper fra kapittelet med korte definisjoner.
En abstrakt sammenheng mellom alle mulige inndata og deres gyldige svar, uavhengig av en bestemt instans.
Ett konkret tilfelle av et problem — for eksempel én bestemt graf vi vil traversere.
Et problem med ja/nei-svar. Grunnformen i kompleksitetsteorien fordi den er enklest å resonnere om.
Et problem der vi søker den beste løsningen etter et mål — for eksempel minst total vekt.
Et problem der vi vil finne et objekt som oppfyller en betingelse, ikke bare avgjøre om det finnes.
Å sjekke at et foreslått svar (sertifikat) faktisk er korrekt. Ofte mye lettere enn å finne svaret.
Å løse problem A ved å oversette instansene til problem B og bruke en løser for B.
En reduksjon der oversettelsen kan beregnes i polynomiell tid og bevarer ja/nei-svaret.
Et kompakt bevis på at svaret er ja, som en verifikator kan kontrollere raskt.
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.
Polynomiell reduksjon
Problem reduseres polynomielt til dersom en polynomiell transformasjon gjør hver -instans om til en -instans med samme ja/nei-svar. Da er minst like hardt som .
Reduksjon bevarer løsbarhet
Kan vi løse effektivt, kan vi løse effektivt ved å oversette først. Kontrapositivt: er hardt, er det også.
Optimerings- vs. beslutningsversjon
Et optimeringsproblem har en tilhørende beslutningsversjon: «finnes en løsning minst så god som ?». De er polynomielt ekvivalente via binærsøk på .
Verifikasjon i polynomiell tid
Et ja-svar har et sertifikat (en mulig løsning) som en verifikator kan sjekke raskt. Grunnlaget for definisjonen av NP.
Komposisjon av reduksjoner
Polynomielle reduksjoner kan settes sammen — summen og komposisjonen av polynomer er fortsatt et polynom. Dette lar oss bygge kjeder av hardhetsbevis.
Læringsmål
Hva du skal kunne etter å ha lest kapittelet.
- 01Skille et problem fra en instans, og forklare hvorfor en algoritme må svare riktig på hver instans
- 02Sammenligne søke-, beslutnings- og optimeringsproblemer, og koble et optimeringsproblem til beslutningsversjonen via binærsøk
- 03Forklare hva et sertifikat er, og hvorfor verifikasjon kan være langt lettere enn å finne løsningen
- 04Beskrive en polynomiell reduksjon A ≤p B, og bruke den til å overføre både effektivitet og hardhet mellom problemer