The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis
From MaRDI portal
Publication:2272200
DOI10.1007/s00224-007-9030-9zbMath1179.68062MaRDI QIDQ2272200
Publication date: 6 August 2009
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-007-9030-9
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Bases for Boolean co-clones
- Succinct representation, leaf languages, and projection reductions
- Relating polynomial time to constant depth
- Nondeterministic \(NC^1\) computation
- The complexity of the descriptiveness of Boolean circuits over different sets of gates
- COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE
- Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
- The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)