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

被引：1

作者：

Atserias, Albert ^{[1
]}

Buss, Sam ^{[2
]}

Muller, Moritz ^{[3
]}

机构：

[1] Univ Politecn Cataluna, Barcelona, Spain

[2] Univ Calif San Diego, San Diego, CA USA

[3] Univ Passau, Passau, Germany

来源：

PROCEEDINGS OF THE 55TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2023 | 2023年

关键词：

bounded arithmetic; non-deterministic exponential-time; polynomial-size circuits; pigeonhole principle; polynomial-time hierarchy; SEARCH; SIZE;

D O I：

10.1145/3564246.3585253

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 not subset of 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. Additionally, we establish a magnification result on the hardness of proving circuit lower bounds.

引用

页码：1257 / 1270

页数：14