Problém s hodnotou obvodu - Circuit Value Problem - Wikipedia
Příklad booleovského obvodu
The Problém s hodnotou obvodu (nebo Circuit Evaluation Problem) je výpočetní problém výpočtu výstupu daného Booleovský obvod na daném vstupu.
Problém je úplný P pod uniformou AC0 redukce. Všimněte si, že pokud jde o časová složitost, to lze vyřešit v lineární čas jednoduše a topologické třídění.
The Problém s booleovskou hodnotou vzorce (nebo Boolean Formula Evaluation Problem) je speciální případ problému, když je obvodem strom. Problém s booleovskou hodnotou vzorce je pro NC1.[1]
Problém úzce souvisí s Booleovský problém uspokojivosti který je kompletní pro NP a jeho doplněk Problém výrokové tautologie, což je kompletní pro co-NP.
Reference
- ^ Buss, Samuel R. (Leden 1987). „Problém s booleovskou hodnotou vzorce je v ALOGTIME“. www.math.ucsd.edu. Citováno 5. května 2017.
 | Tento programování související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to. |