Title: On the Power of Nondeterministic Circuits and Co-Nondeterministic Circuits
Abstract: Revealing the power of nondeterministic computation and co-nondeterministic computation is one of the central problems in computational complexity. In this paper, we consider the two computation and deterministic computation in Boolean circuits. We give the first separations on the power of deterministic circuits, nondeterministic circuits, and co-nondeterministic circuits in general circuits. More precisely, we prove the following facts. There is an explicit Boolean function f such that the nondeterministic \(U_2\)-circuit complexity of f is at most \(2n + o(n)\) and the deterministic and co-nondeterministic \(U_2\)-circuit complexity of f is \(3n - o(n)\). There is an explicit Boolean function f such that the co-nondeterministic \(U_2\)-circuit complexity of f is at most \(2n + o(n)\) and the deterministic and nondeterministic \(U_2\)-circuit complexity of f is \(3n - o(n)\).
Publication Year: 2021
Publication Date: 2021-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot