NP-úplnost
Splnitelnost logického obvodu
 Vytisknout studijní materiál

Splnitelnost logického obvodu

Zatím jsem nedokázali, že některý problém je NP-úplný. Ukážeme, že problém splnitelnosti logického obvodu je NP-úplný.

Kombinační logický obvod sestává z logických hradel, která realizují jednoduché logické funkce. Základní hradla realizují negaci, logický součin a logický součet (obr.). Logický kombinační obvod vznikne připojením výstupů logických hradel na vstupy jiných. Vstupy hradel, ke kterým není připojen výstup žádného hradla jsou vstupy obvodu. Výstupy hradel, které nejsou připojeny na žádný vstup jsou výstupy kombinačního obvodu. Logické kombinační obvody jsou základem počítačového hardwaru vykonávajícího instrukce.

Například součet dvou jednobitových hodnot realizuje obvod na obr.. Jeho vstupy jsou dva operandy, horní výstup je jejich součet a spodní výstup je přenos. Můžeme se o tom přesvědčit připojením všech čtyřech možných dvojic hodnot 0 a 1 na vstupy. Ze dvou takových obvodů lze sestavit obvod pro součet tří hodnot - operandů a přenosu. Sčítačku pro n-bitů pak můžeme získat jejich seřazením za sebou a propojením výstupu pro přenos na vstup pro přenos následujícího. Intuitivně by mělo být zřejmé, že právě tímto způsobem jsou postaveny současné počítače.

Pravdivostní přiřazení je množina logických vstupních hodnot. Obvod s jedním výstupem je splnitelný, má-li pravdivostní přiřazení, pro které je jeho výstup 1. Příklad splnitelného obvodu je na obr. a příklad nesplnitelného obvodu je na obr., jak se opět můžeme přesvědčit.

Problém splnitelnosti obvodu

Problém splnitelnosti obvodu je následující.

Je zadaný logický kombinační obvod, složený z hradel pro negaci, logický součin a logický součet, splnitelný?

Velikost problému je dána počtem hradel a jejich propojení. Podobně jako v případě grafu je jeho zakódování polynomiální. Dokážeme, že problém splnitelnosti obvodu splňuje obě podmínky pro NP-úplný problém.

Tvrzení 1

Problém splnitelnosti obvodu patří do třídy NP.

Připomeňme, že problém patří do třídy NP existuje-li časově polynomiální verifikační algoritmus se dvěma vstupy, který může řešení problému ověřit/verifikovat. V našen případě je prvním vstupem zakódovaná instance problému - logický kombinační obvod L a druhým vstupem je certifikát - pravdivostní přiřazení.

Verifikační algoritmus pro problém splnitelnosti obvodu z pravdivostního přiřazení hodnot vstupům obvodu postupně vypočte výstup všech hradel. Je-li výstup obvodu 1, vstupní hodnoty jsou splňující pravdivostní přiřazení a algoritmus verifikační algoritmus vrátí 1 jinak vrátí 0.

Uvedený algoritmus je časově polynomiální v závislosti na velikosti instance problému L, takže problém splnitelnosti obvodu patří do třídy NP.

Tvrzení 2

Problém splnitelnosti je NP- těžký.

Máme dokázat, že každý rozhodovací problém SÎNP je polynomiálně převeditelný na problém splnitelnosti obvodu. Vraťme se k obrázku pro převeditelnost problému (obr.). Problém T je nyní problém splnitelnosti obvodu a problém SÎNP. Naším úkolem tedy je opsat časově polynomiální algoritmus F, který každou instanci x problému S zobrazí na obvod Lx = f(x) tak, aby S(x) = 1 právě tehdy, když obvod Lx je splnitelný. Protože SÎNP, existuje pro něj časově polynomiální verifikační algoritmus A(x,y), kde x je instance problému S a y odpovídající certifikát. Ukážeme algoritmus F, který pro x vytvoří obvod Lx.

Vstupy pro logické obvody hardwaru počítače jsou hodnoty uložené v paměti a v registrech. Stav výpočtu je dán obsahem těchto pamětí a budeme ho nazývat konfigurací. Vykonáním instrukce nastane změna konfigurace, která bude vstupem hardwaru pro další instrukci. Označme H logický obvod vyjadřující hardware vykonávajícící instrukce a tím zobrazení jedné konfigurace na následující. Verifikační algoritmus A, protože je časově polynomiální, potřebuje v nejhorším případě pro instanci probému o velikosti n = | x | vykonat T(n) = O(nk) instrukcí a velikost certifikátu y je O(nk). Algoritmus F potom pro x vytvoří obvod Lx jako sekvenci T(n) logických obvodů H (obr.), kde počáteční konfigurace c0 obsahuje kód programu pro algoritmus A, instanci problému x a certifikát y. Poslední konfigurace cT(n) někde v pracovní paměti obsahuje výstup algoritmu A.

Vstupem Lx je konfigurace c0 a výstupem konfigurace cT(n). V konfiguraci c0 kromě certifikátu y jsou osatní hodnoty pevné a tedy vstupem Lx zůstává y. Z výstupu ignorujeme všechno, kromě bitu, na kterém je výstup A.

Takto vytvořený obvod Lx počítá Lx(y) = A(x,y) pro jakýkoliv vstup y .

Zopakujme co je naším úkolem. Za prvé musíme ukázat, že Lx je splnitelný právě tehdy, když S(x) = 1, tedy když existuje certifikát y, pro který je A(x,y) = 1. Za druhé musíme ukázat, že čas výpočtu F je polynomiální.

Na to, aby jsme ukázali první vlastnost, předpokládejme, že existuje certifikát y, pro který A(x,y) =1. Jestliže bity y budou na vstupech Lx, potom Lx(y) = A(x,y) = 1 a existuje-li certifikát, Lx je splnitelný. Je-li Lx splnitelný, potom existuje vstup y, pro který Lx(y) = 1 a tedy i A(x, y) = 1.

Zůstáva ukázat, že čas výpočtu F je polynomiální. Napřed ukážeme, že velikost konfigurace je polynomiální v n. Velikost vstupu x algoritmu F je n . Velikost programu pro A je konstantní a velikost certifikátu y je O(nk). Protože algoritmus A je časově polynomiální, také pracovní paměť je O(nk).

Kombinační obvod H má velikost polynomiální ve velikosti konfigurace, která je polynomiální, je tedy polynomiální v n. Obvod Lx má nejvíce T(n) = O(nk) kopií H a jeho velikost je polynomiální v n. Protože čas všech kroků konstrukce obvodu Lx pro x algoritmem F je polynmiální, konstrukce obvodu Lx může být provedena v polynomiálním čase.

Ukázali jsme, že problém splnitelnosti obvodu je NP - úplný.