Kompleksitetsklassene

Klassifisering av hvor mye tid og rom som kreves for å løse et problem.xxxxx

---

De fire (hoved) kompleksitetsklassene

• P problem
• NP problem
• NP-komplett problem (NPC)
  • NPC problemer
• NP-harde problemer (NPH)

---

Et viktig spørsmål som baserer seg på kunnskap ovenfra: P=NP

---

Eksempler

Hamiltonian cycle problemet (NP)

Hamiltonian cycle problemet (HAM-CYCLE)

Gitt en rettet graf, $G=(V,E)$, eksisterer det en enkel sykel som går innom alle noder i grafen? Dette er et NP problem, fordi det har ingen kjent løsning i polynomisk tid, men vi kan enkelt verifisere et forslag til løsning/sertifikat i polynomisk tid.

Link to original