NP-komplett problem (NPC)

Et problem er NP-komplett hvis den er i NP, og alle problemer i NP må kunne reduseres (Redusibilitet) til dette problemet.

Altså er et NPC problem minst like vanskelig som alle andre NP problemer

---

Egenskaper:

• Alltid et Beslutningsproblem
• NPC problemer er en delmengde av NP problemer, og er de vanskeligste problemene å løse.

$$NPC\subseteq NP$$

• Dersom man kan finne løsningen til et NPC problem, kan man løse alle NPC problemene.

For å vise at et problem er i NPC må vi redusere fra NPC.

---

NP-komplett ved formelle språk

Et språk (problem), $L$, er NP-komplett problem (NPC) dersom

$$\begin{array}{rl}& L\in NP\\ & L_0\le L\text{for alle}{L}_0\in NP\end{array}$$Link to original

Problemer

Hvordan bevise NPC generelt

Hvordan kan man bevise NPC generelt?

1. Evt gjør om problemet til et beslutningsproblem.
2. Bevis at det er verifiserbart i polynomisk tid.
3. Bevis at problemet er NPH (via en reduksjon).

Link to original

---

NPC problemer

CIRCUIT-SAT SAT 3-CNF-SAT CLIQUE VERTEX-COVER Hamiltonian cycle problemet (HAM-CYCLE) Traveling Salesman Problem (TSP) SUBSET-SUM

Link to original