Matematické Fórum

iFR3NK · 28. 08. 2010 19:38

Dobrý den,

učím se na zkoušku z Teorie grafů a diskrétní optimalizace a stále mi není jasný problém splnitelnosti logických formulí (SAT) a jeho modifikace.

Co jsem vyčetl:
- Dle Cookovy věty platí, že SAT je NPC
- podle jedné z vět 2-SAT je P
- dle důkazu je 3-SAT NPC a lze na něj redukovat SAT

Co nechápu:
- proč 2-SAT není také NPC, když je speciálním případem SAT?
- když mohu redukovat SAT na 3-SAT, proč nemohu redukovat ještě o jeden literál méně a dostat se tak na 2-SAT?

Možná mi stále i po několikanásobném přečtení výkladu celé problematiky nedochází ta hranice mezi P, NP a NPC. Přečetl jsem toho i spoustu, co mi vrátil google, ale stále mi to není úplně jasné :(

Děkuji za odpověď.

Kondr · 08. 10. 2010 17:38

To, že SAT je NPC znamená, že neexistuje polynomiální algoritmus, který pro každou instanci SATu vrátí správný výsledek. Existují ale algoritmy, které v polynomiálním čase řeší speciální instance SATu. Např. algoritmus pro 2-SAT najdeš na webu, pro instance 3-SATu bez negovaných literálů napíše program taky každý (return true).

Redukce na 3-sat funguje tak, že přidávám nové proměnné, každá nová proměnná mi substituuje něco složitějšího. Kdybych mohl ale přidanou proměnnou dát jen do kluzule o dvou literálech, substituovala by pouze jinou proměnnou, což nám k řešení problému nepomůže.

Osiris · 09. 10. 2010 11:51

Kondr napsal(a):
To, že SAT je NPC znamená, že neexistuje polynomiální algoritmus, který pro každou instanci SATu vrátí správný výsledek. Existují ale algoritmy, které v polynomiálním čase řeší speciální instance SATu. Např. algoritmus pro 2-SAT najdeš na webu, pro instance 3-SATu bez negovaných literálů napíše program taky každý (return true).

Redukce na 3-sat funguje tak, že přidávám nové proměnné, každá nová proměnná mi substituuje něco složitějšího. Kdybych mohl ale přidanou proměnnou dát jen do kluzule o dvou literálech, substituovala by pouze jinou proměnnou, což nám k řešení problému nepomůže.

Já si myslím, že je nutné předpokládat, že $P\neq NP$ . V opačném případě první věta neplatí.

Matematické Fórum

#1 28. 08. 2010 19:38

[Teorie Grafů] SAT, 2-SAT, 3-SAT problémy a P, NP, NPC

#2 08. 10. 2010 17:38

Re: [Teorie Grafů] SAT, 2-SAT, 3-SAT problémy a P, NP, NPC

#3 09. 10. 2010 11:51

Re: [Teorie Grafů] SAT, 2-SAT, 3-SAT problémy a P, NP, NPC

Kondr napsal(a):

Zápatí