NP-polnost

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Najprej naredimo kvocientno oz. faktorsko množico NP/~ razreda NP z relacijo ~ polinomska ekvivalenca. Tako dobimo množico, ki je delno urejena glede na relacijo polinomska prevedljivost. Maksimalni element te množice imenujemo razred NP-c ali razred NP-polnih problemov.

Velja: Problem A je NP-poln, če spada v razred NP in lahko vsak problem iz razreda NP polinomsko prevedemo na A.

Znano je, da je problem SAT NP poln.

Glej tudi

Osebna orodja