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

共 31 条

[1] On the consistency of circuit lower bounds for non-deterministic time
Atserias, Albert
Buss, Sam
Mueller, Moritz
JOURNAL OF MATHEMATICAL LOGIC, 2024,
[2] Polynomial time ultrapowers and the consistency of circuit lower bounds
Jan Bydžovský
Moritz Müller
Archive for Mathematical Logic, 2020, 59 : 127 - 147
[3] Polynomial time ultrapowers and the consistency of circuit lower bounds
Bydzovsky, Jan
Mueller, Moritz
ARCHIVE FOR MATHEMATICAL LOGIC, 2020, 59 (1-2) : 127 - 147
[4] Amplifying circuit lower bounds against polynomial time, with applications
Lipton, Richard J.
Williams, Ryan
COMPUTATIONAL COMPLEXITY, 2013, 22 (02) : 311 - 343
[5] Amplifying Circuit Lower Bounds Against Polynomial Time With Applications
Lipton, Richard J.
Williams, Ryan
2012 IEEE 27TH ANNUAL CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC), 2012, : 1 - 9
[6] On Exponential-time Hypotheses, Derandomization, and Circuit Lower Bounds
Chen, Lijie
Rothblum, Ron D.
Tell, Roei
Yogev, Eylon
JOURNAL OF THE ACM, 2023, 70 (04)
[7] State agnostic planning graphs: deterministic, non-deterministic, and probabilistic planning
Bryce, Daniel
Cushing, William
Kambhampati, Subbarao
ARTIFICIAL INTELLIGENCE, 2011, 175 (3-4) : 848 - 889
[8] Circuit lower bounds in bounded arithmetics
Pich, Jan
ANNALS OF PURE AND APPLIED LOGIC, 2015, 166 (01) : 29 - 45
[9] Nonuniform ACC Circuit Lower Bounds
Williams, Ryan
JOURNAL OF THE ACM, 2014, 61 (01)
[10] Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits
Chen, Lijie
2019 IEEE 60TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2019), 2019, : 1281 - 1304

← 1 2 3 4 →