Lower Bounds for the Size of Nondeterministic Circuits

DOI10.1007/978-3-319-21398-9_23zbMath1465.68079arXiv1504.06731OpenAlexW1735577759MaRDI QIDQ3196391

Hiroki Morizumi

Publication date: 29 October 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1504.06731

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (1)

On the power of nondeterministic circuits and co-nondeterministic circuits

Cites Work

• A Boolean function requiring 3n network size
• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
• Graph-theoretic properties in computational complexity
• An Elementary Proof of a 3n − o(n) Lower Bound on the Circuit Complexity of Affine Dispersers
• Explicit lower bound of 4.5n - o(n) for boolena circuits
• Computational Complexity
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Lower Bounds for the Size of Nondeterministic Circuits