NP-Kompletthet

Et klasse problemer som er både vanskelige å løse, men lette å verifisere.

NP - Nondeterministic polynomial

---

Begreper

• Skille mellom Optimeringsproblemer og Beslutningsproblem

---

Undertemaer

• Redusibilitet
• Kompleksitetsklassene
  • Hvordan bevise NPC generelt

---

• Abstrakte problemer
• Enkoding
• Formelle språk
• Verifikasjonsalgoritme
• NP definert ved formelle språk
• Co-NP definert ved formelle språk
• Reduksjon ved formelle språk
• NP-komplett ved formelle språk