Matching: Delmengde $M ⊆ E$ for en urettet graf $G = (V,E)$
Input: En bipartitt urettet graf $G = (V,E)$
Output: En matching $M ⊆ E$ med flest mulig kanter, dvs., der $|M|$ er maksimal.
For heltallskapasiteter gir Ford-Fulkerson heltallsflyt
Et problem er en relasjon mellom input og output. Jobben vår er å produsere gyldig output fra input.
Et problem kalles konkret hvis input og output er bitstrenger.
En verifikasjonsalgoritme sjekker om løsningen stemmer.
Kaller gjerne en løsning et sertifikat eller et vitne
Generelt: Egentlig et hvilket som helst ja/nei-spørsmål
Problem med språk:
Konkrete beslutningsproblemer tilsvarer formelle språk (mengder av strenger). Ja-instanser er med, nei-instanser er ikke.
Accept, reject, decide
En algoritme $A$ aksepterer $x$ dersom $A(x) = 1$. Den avviser $x$ dersom $A(x) = 0$ Den avjør et språk $L$ dersom..
- $x \in L \rightarrow A(x) = 1$
- $x \not\in L \rightarrow A(x) = 0$
Accept vs decide:
Selv om $L$ er språket som aksepteres av $A$, så trenger ikke $A$ avgjøre $L$, siden den kan la være å svare for nei-instanser (ved å aldri terminere)
Kompleksitetsklasse:
En mengde språk
P:
Språkene som kan avgjøres i polynomisk tid. Også de som kan aksepteres i polynomisk tid!(Theorem 34.2)
Cobham’s tese:
Det er disse problemene vi kan løse i praksis
Sertifikat:
En streng $y$ som brukes som “bevis” for et ja-svar
Verifikasjonsalgoritme:
Tar inn sertifikat $y$ i tillegg til instans $x$ En algoritme $A$ verifiserer $x$ hvis det eksiterer et sertifikat $y$ slik at $A(x,y) = 1$
Intuitivt:
Algoritmen “sjekker svaret”. Om en graf har en Hamilton-sykel, kan sertifikatet være noderekkefølgen i sykelen.
Asymmetrisk:
Den finnes ikke “motbevis” eller “anti-sertifikat”
NP:
Språkene som kan verifieres i polynomisk tid
N = Nondeterministic: Kan løses om vi klarer “gjette” sertifikater
HAM-CYCLE:
Språket for Hamilton-sykel-problemet
$HAM-CYCLE ∈ NP$
Lett å verifiere i polynomisk tid Merk: Ikke nødvendigvis lett å falsifiere
co-NP:
Språkene som kan falsifieres i polynomisk tid
F.eks. TAUTOLOGY
P vs NP:
Om vi kan løse problemet, så kan vi verifisere det med samme algoritme, og bare ignorere sertifikatet Dvs.: $P \subseteq NP$ og $P \subseteq co-NP$
Vi vet ikke om $P = NP \cap co-NP$
Mest plausibelt at $P \subset NP \cap co-NP$
Instans: En krets med logiske porter og én utverdi
Spørsmål: Kan utverdien bli 1?
Instans: En logisk formel
Spørsmål: Kan formelen være sann?
Instans: En logisk formel på 3-CNF-form
Spørsmål: Kan formelen være sann?
Instans: Mengde positive heltall $S$ og positive heltall $t$
Spørsmål: Finnes en delmengde $S’ \subseteq S$ så $\Sigma_{s ∈ S’}s = t$
Instans: En urettet graf $G$ og et heltall $k$
Spørsmål: Har $G$ en komplett delgraf med $k$ noder?
Instans: En urettet graf $G$ og et heltall $k$
Spørsmål: Har $G$ et nodedekke med $k$ noder? Dvs., $k$ noder som tilsammen ligger inntil alle kanter
Instans: En urettet graf $G$
Spørsmål: Finnes det en sykel som inneholder alle nodene?
Instans: En komplett graf med heltallsvekter og et heltall $k$
Spørsmål: Finnes det en en rundtur med kostnad $⩽ k$?
La oss si du har funnet to skattekister. Du ønsker å si noe om hvor vanskelige de er å åpne. Anta at B inneholder nøkkelen (løsningen) til A.
Kan det nå være vanskeligere å åpne A enn B?
Nei! Om vi kan åpne B, kan vi naturligvis åpne A som en følge.
Vi har redusert problemet “åpne A” til problemet “åpne B”
Input: En bitstreng $x$
Output: En bitstreng $f(x)$, der
Om vi kan avgjøre om $f(x) \in L_2$ kan vi avgjøre om $x /in L_1$
Redusibilitet:
Hvis $A$ kan reduseres til $B$ i polynomisk tid, skriver vi $A \leqslant B$
Ordning:
Relasjonen $\leqslant p$ utgjør en preordning
Hardhetsbevis:
For å vise at $B$ er vanskelig, redusér fra et vanskelig problem $A$ dvs., etablér at $A \leqslant B$
Kompletthet:
Et problemt er komplett or en gitt klasse og en gitt type reduksjoner dersom det er maksimalt for redusibilitetsrelasjonen
Maksimalitet:
Et element er maksimalt dersom alle andre er mindre eller lik. For reduksjoner: $Q$ er maksimalt dersom alle problemer i klassen kan reduseres til $Q$.
NPC:
De komplette språkene i NP, under polynomiske reduksjoner
De vanskelige problemene fra tidligere er altså eksempler på NP-komplette problemer
NP-hardhet:
Et problem $Q$ er NP-hardt dersom alle problemer i NP kan reduseres til det. Et problem er altså NP-komplett dersom det…
- er NP-hardt, og
- er i NP