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.68062OpenAlexW2130665499MaRDI 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
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
A note on the expressibility problem for modal logics and star-free regular expressions ⋮ On the complexity of the clone membership problem
Cites Work
- 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)
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item