2015/04/25 by Hiroki Morizumi, Morizumi, Hiroki
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences #cs.CC #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1504.06731
the submitted version to COCOON'15
arxiv created 2015/04/25 · openalex publication_date 2015/04/25 · arxiv updated 2015/04/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Nondeterministic circuits are a nondeterministic computation model in circuit complexity theory. In this paper, we prove a 3(n-1) lower bound for the size of nondeterministic U2-circuits computing the parity function. It is known that the minimum size of (deterministic) U2-circuits computing the parity function exactly equals 3(n-1). Thus, our result means that nondeterministic computation is useless to compute the parity function by U2-circuits and cannot reduce the size from 3(n-1). To the best of our knowledge, this is the first nontrivial lower bound for the size of nondeterministic circuits (including formulas, constant depth circuits, and so on) with unlimited nondeterminism for an explicit Boolean function. We also discuss an approach to proving lower bounds for the size of deterministic circuits via lower bounds for the size of nondeterministic restricted circuits.