On the Consistency of Circuit Lower Bounds for Non-Deterministic Time

2023/03/02 by Albert Atserias, Sam Buss, Atserias, Albert +3 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Machine Learning and Algorithms #Numerical Methods and Algorithms

paper · pdf · doi:10.48550/arxiv.2303.01016

openalex publication_date 2023/03/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove the first unconditional consistency result for superpolynomial circuit lower bounds with a relatively strong theory of bounded arithmetic. Namely, we show that the theory V⁰₂ is consistent with the conjecture that NEXP \not⊆ P/poly, i.e., some problem that is solvable in non-deterministic exponential time does not have polynomial size circuits. We suggest this is the best currently available evidence for the truth of the conjecture. The same techniques establish the same results with NEXP replaced by the class of problems that are decidable in non-deterministic barely superpolynomial time such as NTIME(n^{O(logloglog n)}). Additionally, we establish a magnification result on the hardness of proving circuit lower bounds.

Cited by

• A Logspace Constructive Proof of L=SL

Related

• Some Results on the Circuit Complexity of Bounded Width Circuits and Nondeterministic Circuits
• Polynomial formulations as a barrier for reduction-based hardness proofs
• A Superpolynomial Lower Bound on the Size of Uniform Non-constant-depth Threshold Circuits for the Permanent
• A Casual Tour Around a Circuit Complexity Bound
• Relationship between circuit complexity and symmetry