(3,3)-SAT
Úloha číslo: 3772
Uvažujme logickou formuli tvaru \((x_1 \lor \lnot x_2 \lor \ldots) \land (x_3 \lor \ldots) \land \ldots\), tedy takovou, která je konjunkcí klauzulí, což jsou disjunkce literálů a každý literál je buďto proměnná nebo její negace. Formule je splnitelná, pokud je za proměnné možné dosadit pravda/nepravda tak, aby celá formule byla pravdivá. Dokažte, že libovolná formule, jejíž každá klauzule obsahuje právě 3 literály a každá proměnná se vyskytuje v právě 3 různých klauzulích, je splnitelná.
Nápověda
Převeďte na problém hledání párování v grafu.
Řešení
Vytvoříme bipartitní graf incidence, kde na jedné straně jsou klauzule a na druhé proměnné, které se v nich vyskytují a to buď jako pozitivní nebo jako negativní literál.
Tento graf je 3-regulární bipartitní, proto obsahuje perfektní párování.
Perfektní párování určí pro každou klauzuli, která proměnná zaručí její splnění. Hodnotu proměnné nastavíme na {\sf pravda}, pokud se v klauzuli vyskytuje jako pozitivní literál; a {\sf nepravda} v opačném případě.
Poznámka: pokud by se některá proměnná vyskytovala vícekrát ve stejné klauzuli, nijak by to splnitelnost neovlivnilo. Ve grafu incidence by takové případy způsobily vícenásobné hrany. Trojnásobné hrany tvoří komponenty – ty se ošetří snadno. Je-li \((u,v)\) dvojnásobná hrana, lze \(u\) a \(v\) z grafu vyjmout a spojit hranou jejich zbylé sousedy. Tato operace neovlivní existenci perfektního párování (ani hranové tříbarevnosti).
Všimněte si, že \((k,k)\)-SAT je vždy splnitelný, pokud mají proměnné výskyty v různých klauzulích. Ovšem popsaná redukce násobných hran funguje jen pro \((3{,}3)\)-SAT.
