V teorii složitosti , je kombinační obvod je výpočtový model skládá z logických hradel ( logických funkcí ) spojených dohromady. Toto je jeden způsob reprezentace booleovské funkce .
Booleovský obvod lze použít k rozpoznání formálního jazyka , tj. K rozhodnutí, zda slovo patří do konkrétního jazyka. Vlastnosti obvodů, které rozpoznávají jazyk, umožňují definovat (nebo předefinovat) třídy složitosti.
Booleovské obvody jsou modelem používaným v počítačovém inženýrství, zejména pro návrh aritmetických a logických jednotek a v teoretické informatice, zejména pro stanovení dolních mezí.
Booleovský obvod je konečný připojený acyklický směrovaný graf ( DAG ), jehož listy jsou vstupy a jedinečný kořen je výstup. Vrcholy jsou brány, obvykle brány AND , OR a NOT . Můžeme rekurzivně vyhodnotit výstupní hodnotu z listů: například pro bránu „AND“, pokud jsou vstupy kladné, bude výstup kladný, jinak bude záporný.
Vzorec výrokové logiky je speciální případ booleovského obvodu, kterým je strom.
Můžeme také modelovat obvody přímými programy : jsou to programy bez podmíněnosti a bez smyček. Například logický obvod na obrázku je ekvivalentní následujícímu přímočarému programu, volá x 1 a x 2 vstupy a zavádí proměnné y 1 , y 2 , y 3 pro tři logická hradla :
y1 := x1 ou x2 y2 := non x2 y3 := y1 et y2Klasické obvody rozhodují, které jazyky jsou kódovány v binárním formátu: první bit slova je první vstup atd. Slovo je přijato tehdy a jen tehdy, pokud je výstup obvodu pravdivý . Protože obvod dokáže rozpoznat pouze slova stejné velikosti, obecně mluvíme o rodině obvodů , kde jsou rozpoznávána slova jazyka velikosti . Vzor, jako je tento, kde pro každou velikost vstupu existuje jiný obvod, se nazývá nejednotný .
Booleovské obvody, stejně jako jiné výpočetní modely, jako jsou Turingovy stroje, umožňují definovat třídy složitosti. Třída složitosti seskupuje algoritmické problémy podle využití zdrojů (času, paměti atd.), Které jsou potřebné k jejich rozhodování. Zde prezentované třídy založené na obvodech definují třídy složitosti, kde jsou prostředky:
Zde jsou příklady tříd složitosti, které lze definovat s obvody.
Lupanov v roce 1952 ukazuje, že jakákoli booleovská funkce na n proměnných připouští obvod o velikosti (1 + o (1)) 2 n / n.
Shanon v roce 1949 ukazuje, že pro všechna n> 1 existuje booleovská funkce s n proměnnými, která nepřipouští obvod o velikosti 2 n / (10n). Další výhodou booleovských obvodů je jejich jednoduchost (ve srovnání s Turingovými stroji ), která umožňuje prokázat určité spodní hranice typu: obvody rozpoznávající daný jazyk musí mít alespoň velikost . Tento druh terminálu umožňuje rozlišovat určité třídy. Avšak nalezení dobrého dolní hranice pro obvody je považován za obtížný, a v některých případech je možné dokázat, že klasické techniky nemůže pracovat, jako je tomu u fyzických důkazů pro P = NP problém . Známá dolní hranice je, že paritní funkce nepatří do AC 0 .
Problém vyhodnocení obvod , který spočívá v rozhodování o tom, výstup obvodu na dané vstupy, je problém, P-kompletní.