Øv med flashcards — NP-komplette problemer og bevis

Kapittel 14 · TDT4120

1 / 14

14 kort

Formel

Reduksjon for NP-kompletthetsbevis

Formel

B \in NPC : B \in NP \land A \leq_{p} B for et kjent A \in NPC

For å vise at $B$ er NP-komplett: vis at $B$ er i NP, og reduser et allerede kjent NP-komplett problem $A$ til $B$ .

Tips: bruk piltastene for å bla og mellomrom/Enter for å snu kortet.