On the power of nondeterministic circuits and co-nondeterministic circuits

DOI10.1007/978-3-030-68195-1_9OpenAlexW3132573772MaRDI QIDQ2232269

Hiroki Morizumi

Publication date: 4 October 2021

Full work available at URL: https://doi.org/10.1007/978-3-030-68195-1_9

zbMATH Keywords

circuit complexity\(U_2\)-circuitco-nondeterministic circuitnondeterministic circuit

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
• Lower Bounds for the Size of Nondeterministic Circuits
• A $4n$ Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions
• Explicit lower bound of 4.5n - o(n) for boolena circuits

This page was built for publication: On the power of nondeterministic circuits and co-nondeterministic circuits