On the Power of Small-Depth Computation
Emanuele Viola
Broschiertes Buch

On the Power of Small-Depth Computation

Versandkostenfrei!
Versandfertig in 1-2 Wochen
68,99 €
inkl. MwSt.
PAYBACK Punkte
34 °P sammeln!
The NP-completeness of SAT is a celebrated example of the power of bounded-depth computation: the core of the argument is a depth reduction establishing that any small nondeterministic circuit - an arbitrary NP computation on an arbitrary input - can be simulated by a small non deterministic circuit of depth 2 with unbounded fan-in - a SAT instance. Many other examples permeate theoretical computer science. On the Power of Small-Depth Computation discusses a selected subset of them, and includes a few unpublished proofs. On the Power of Small-Depth Computation starts with a unified treatment o...