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

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 ‍⊈ ‍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.

Authors

• Albert Atserias
• Sam Buss
• Moritz Müller

Keywords

• bounded arithmetic
• non-deterministic exponential-time
• pigeonhole principle
• polynomial-size circuits
• polynomial-time hierarchy