Föreläsning 9

Question 1

Vad står P för i P vs NP?

Answer 1

P är settet av alla problem som kan lösas på polynomiell tid

Question 2

Vad står NP för i P vs NP?

Answer 2

NP är settet av alla problem som kan valideras på polynomiell tid

Question 3

Vad är ett NP svårt problem?

Answer 3

Ett problem utan kända lösningar på polynomiell tid. Ett NP-svårt problem måste inte vara i NP.

Question 4

Vad är ett NP komplett problem?

Answer 4

Ett NP svårt problem, som också är med i NP

Question 5

Hur visar man att ett problem X är NP komplett?

Answer 5

Du visar att ett annat NP komplett problem kan reduceras till X.

Question 6

Hur visar man att problemet att finna en hamiltonisk cykel är NP-komplett?

Answer 6

Man kan reducera godtyckliga 3-SAT problem till en hamiltonsk cykel, vilket implicerar att detta problem är i samma svårighetsklass (NPC).

Question 7

Vad innebär traveling salesman problem?

Answer 7

Hitta den billigaste cykeln genom alla noder i en viktad graf

Question 8

Hur visar man att traveling salesman problem är NP-komplett?

Answer 8

Det har visats att problemet med att finna en hamilton cykel är NP-komplett.

Genom att visa att man kan reducera problemet till hamiltoncykel-problemet, kan man påvisa att även detta problem är NP-komplett.

Question 9

Hur visar man att coloring problem är NP-komplett?

Answer 9

Man reducerar 3-SAT till coloring problem. Detta kan göras genom att konstruera grafen på ett sätt så att det endast går att färga den ifall det finns en lösning till uttrycket.