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 条

[21] Circuit lower bounds from learning-theoretic approaches
Kawachi, Akinori
THEORETICAL COMPUTER SCIENCE, 2018, 733 : 83 - 98
[22] Conspiracies Between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness
Oliveira, Igor C.
Santhanam, Rahul
32ND COMPUTATIONAL COMPLEXITY CONFERENCE (CCC 2017), 2017, 79
[23] Upper and Lower Time and Space Bounds for Planning
Backstrom, Christer
Jonsson, Peter
ECAI 2016: 22ND EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE, 2016, 285 : 716 - 724
[24] Lower Bounds for Non-Commutative Skew Circuits
Limaye, Nutan
Malod, Guillaume
Srinivasan, Srikanth
THEORY OF COMPUTING, 2016, 12
[25] STRONG AVERAGE-CASE CIRCUIT LOWER BOUNDS FROM NONTRIVIAL DERANDOMIZATION
Chen, Lijie
Ren, Hanlin
SIAM JOURNAL ON COMPUTING, 2022, 51 (03) : 115 - 173
[26] Time-space lower bounds for the polynomial-time hierarchy on randomized machines
Diehl, Scott
van Melkebeek, Dieter
SIAM JOURNAL ON COMPUTING, 2006, 36 (03) : 563 - 594
[27] Inductive time-space lower bounds for SAT and related problems
Williams, Ryan
COMPUTATIONAL COMPLEXITY, 2006, 15 (04) : 433 - 470
[28] Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP
Murray, Cody
Williams, Ryan
STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2018, : 890 - 901
[29] CIRCUIT LOWER BOUNDS FOR NONDETERMINISTIC QUASI-POLYTIME FROM A NEW EASY WITNESS LEMMA
Murray, Cody D.
Williams, R. Ryan
SIAM JOURNAL ON COMPUTING, 2020, 49 (05)
[30] Inductive Time-Space Lower Bounds for Sat and Related Problems
Ryan Williams
computational complexity, 2006, 15 : 433 - 470

← 1 2 3 4 →