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

DOI10.1145/3564246.3585253arXiv2303.01016OpenAlexW4376639678MaRDI QIDQ6428147FDOQ6428147

Albert Atserias, Samuel R. Buss, Moritz Müller

Publication date: 2 March 2023

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${}_2^0$ is consistent with the conjecture that NEXP $otsubseteq$ 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(logloglogn)})$. Additionally, we establish a magnification result on the hardness of proving circuit lower bounds.

Full work available at URL: https://doi.org/10.1145/3564246.3585253

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited In (2)

• Mathematical logic: proof theory, constructive mathematics. Abstracts from the workshop held November 12--17, 2023
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024

This page was built for publication: On the Consistency of Circuit Lower Bounds for Non-Deterministic Time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6428147)