[Oppgave] [Levering] [Løsningsforslag]
Innleveringsfrist: 20.11.2017 15:00
Du er logget inn og får derfor se om du har svart riktig/feil på de enkelte oppgavene. LF-svar er markert med grønt og feil svar er markert med rødt.
Hvis dere er uenige i fasit, oppfordres dere til å diskutere dette på Piazza.
a) Hva er maks flyt-problemet? (4.8 %)
b) Hva betyr notasjonen 11/16 mellom node $s$ og $v_1$? (4.8 %)
c) Hva er galt med dette flytnettverket? (4.8 %)
d) Hva er $f(v_3, v_2)$ i dette flytnettverket? (4.8 %)
e) Hva er galt med dette flytnettverket? (4.8 %)
f) Hva er $c_f(v_3, v_2)$ i dette flytnettverket? (4.8 %)
g) Hvor stor er flyten $|f|$ i følgende graf? (4.8 %)
h) Hvilke av disse stiene er en flytforøkende sti (augmenting path)? (4.8 %)
i) Hva er maks flyt mellom $s$ og $t$? (4.8 %)
a) Et snitt $(S, T)$ av et nettverk er en partisjonering av nodene $V$ i et nettverk slik at $s \in S$ og $t \in T$ og gjelder $T = V + S$. (4.8 %)
b) Hva er et minimalt snitt? (4.8 %)
c) Kapasiteten til det minimale snittet trenger ikke nødvendigvis være lik den maksimale flyten for et gitt nettverk. (4.8 %)
a) P $\subseteq$ NP (4.8 %)
b) P $\subseteq$ NPC (4.8 %)
c) NP $\subseteq$ NPC (4.8 %)
d) Dersom vi kan vise at et problem i NP kan løses i polynomisk tid må P=NP. (4.8 %)
Du får oppgitt et problem $X$, og ønsker å finne ut hvilken kompleksitetsklasse problemet tilhører. Hvilke utsagn er sanne?
a) Du sammenlikner $X$ med problemet $Y$, som kan løses i polynomisk tid. (4.8 %)
b) Du sammenlikner $X$ med problemet $Z$, som er NP-komplett. (4.8 %)
Du har problemene $A$, $B$ og $C$. Alle tre er i NP. Du vet at $A$ er i P og $B$ er i NPC. I denne oppgaven menes det med "reduksjon" en reduksjon i polynomisk tid.
a) Hvilken av følgende reduksjoner viser at C er i P? (4.8 %)
b) Hvilken av følgende reduksjoner viser at C er i NPC? (4.8 %)
c) Hvilken av følgende reduksjoner viser at P=NP? (4.8 %)