Avgjørelsesproblemer

Question 1

Når er et problem i P?

Answer 1

Når problemet kan løses i polynomisk tid.

Altså problemer der vi vet det finnes en algoritme som er i O(n^k) for et tall k > 0.

Question 2

Når er et problem i NP?

Answer 2

Når problemet kan verifiseres i polynomisk tid.

Question 3

Hvordan kan vi verifisere at et problem er i NP?

Answer 3

Hvis vi har et problem L, og hvis det finnes en algoritme V som tar en instans av L og et sertifikat som input, og outputter JA for JA-instanser innen polynomisk tid.

Altså vi tar inn en f.eks. en graf og en liste med noder som beskriver en sykel, så verifiserer vi at denne syklen av noder faktisk finnes i grafen.

Question 4

Er P i NP?

Answer 4

Ja, om vi kan løse et problem i polynomisk tid, så kan vi også verifisere det i polynomisk tid.

• Verifiserings algoritmen kan da faktisk bare løse problemet, og trenger ingen sertifikat.

Question 5

Hva er et NP-komplett problem?

Answer 5

NP-komplette problemer er de vanskligste problemene i NP.

Question 6

Hva er polynomtidsreduksjon?

Answer 6

Intuitivt: en måte å si at et avgjørelsesproblem B er minst like vanskelig som et problem A. Vi skriver A ≤p B for dette.

En polynomtidsreduksjon fra A til B er en algoritme som oversetter fra instanser i A til instanser i B slik at

• Alle JA-instanser i A blir oversatt til JA-instanser i B (tilsvarende for NEI-instanser)
• Oversettelsen gjøres i polynomtid

Question 7

Hva vet vi om alle polynomtidsløsbare problemer?

Answer 7

At de kan alle reduseres til hverandre.

Question 8

Når er et problem NP-hardt?

Answer 8

Et problem L er NP hardt hvis
- for alle problemer A i NP, så er A ≤p L

Intuitivt tilsvarer dette at problemet er minst like vanskelig å løse som alle andre problemer i NP.

L er NP-hardt = hvert problem A i NP kan reduseres i polynomtid til L.

• Intuisjonen er at du kan oversette problemer som er lettere eller like vanskelige som et annet problem, til det andre problemet, men ikke motsatt.

Question 9

Når er et problem NP-komplett?

Answer 9

Et avgjørelsesproblem L er NP-komplett hvis

1. L er i NP, og
2. L er NP-hardt

NP-hardt = hvert problem A i NP kan reduseres i polynomtid til L.

Alle andre problemer som er i NP kan oversettes til NP-komplette problemer.
- Intuisjonen er at du kan oversette problemer som er lettere eller like vanskelige som et annet problem, til det andre problemet, men ikke motsatt.

Question 10

Hvordan kan vi vise NP-kompletthet?

Answer 10

Vis medlemskap i NP: vis for eksempel at problemet L kan verifiseres i polynomisk tid.

Vis NP-hardt: velg et “egnet” kjent NP-komplett problem L’ og vis at L’ ≤p L

Question 11

Hva er et avgjørelsesproblem?

Answer 11

Et avgjørelsesproblem er et problem hvor svaret er JA eller NEI.

• “Sorted: Er en liste sortert?”
• “Reachability: Finnes det en sti mellom to par av noder i en graf?”