Splnitelnost: Porovnání verzí

Přidán 1 bajt ,  před 1 rokem
m
Robot: náhrada zastaralé matematické syntaxe podle mw:Extension:Math/Roadmap
(2SAT je P-úplný problém, čo dokazuje jeho redukcia na problém dosiahnutelnosti v grafe, o ktorom sa vie, že je P-úplný.Trieda NL tu nemá čo hladať. reč je o časovej zložitosti, nie priestorovej)
m (Robot: náhrada zastaralé matematické syntaxe podle mw:Extension:Math/Roadmap)
 
'''Literál''' je buď proměnná nebo negace proměnné (negace výrazu může být redukována na negované proměnné pomocí [[De Morganovy zákony|De Morganových zákonů]]). Například <math>\textstyle{x_1}</math> představuje '''pozitivní literál''' a <math>\neg x_2</math> představuje '''negativní literál'''.
 
'''Klauzule''' je [[disjunkce]] literálů. Například <math>x_1 \orlor \neg x_2</math> je klauzule (čti "x-jedna nebo non-x-dva").
 
Existuje několik speciálních případů splnitelnosti, kdy je požadováno, aby ve formuli byly v [[Konjunkce (matematika)|konjunkci]] klauzulí (jedná se formule v [[Konjunktivní normální forma|konjunktivní normální formě]]). Určení splnitelnosti formule v konjunktivní normální formě, kde každá klauzule je omezena na nejvýše tři literály představuje NP-úplný problém, tento problém se nazývá "3SAT", "3CNFSAT", nebo "3-satisfiability". Určení splnitelnosti formule, ve kterém je každá klauzule omezena na nejvýše dva literály je [[P (třída složitosti)|P-úplný]] problém, tento problém se nazývá "[[2SAT]]". Určení splnitelnosti formule, v níž každá klauzule je [[Hornova klauzule]] (tj. obsahuje nanejvýš jeden pozitivní literál) je [[P-úplný]] problém, tento problém se nazývá [[Hornova-splnitelnost]].