Referanseside · Kapittel 33

Begreper & formler

Alle nøkkelbegrepene og formlene fra NP-fullstendighet, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.

Øv med flashcards7 kort fra dette kapittelet

Begreper

Sentrale begreper fra kapittelet med korte definisjoner.

01P

Klassen av problemer som kan løses i polynomisk tid ( $O (n^{k})$ ).

02NP

Klassen av problemer som kan verifiseres i polynomisk tid.

03NP-fullstendig

Problem som er både i NP og så vanskelig som alle andre i NP.

04Reduksjon

Transformasjon av ett problem til et annet på polynomisk tid for å vise kompleksitet.

05SAT-problemet

Det første problemet bevist NP-fullstendig (Cook-Levin-teoremet).

Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.

A \leq_{p} B

NP \subseteq EXP