Unprovability of circuit upper bounds in Cook's theory PV

DOI10.23638/LMCS-13(1:4)2017MaRDI QIDQ2980966zbMATH OpenFDO

Authors Jan Krajíček, Igor C. Oliveira

Publication date 8 May 2017

Full work available at URL https://arxiv.org/abs/1605.00263

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of proofs (03F20) First-order arithmetic and fragments (03F30)

Abstract: We establish unconditionally that for every integer $kgeq1$ there is a language $LinmboxP$ such that it is consistent with Cook's theory PV that $LotinSize(n^k)$. Our argument is non-constructive and does not provide an explicit description of this language.

Recommendations

• Circuit lower bounds in bounded arithmetics
• Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
• Unprovability of consistency statements in fragments of bounded arithmetic
• Consequences of the provability of NP ⊆ P/poly
• Polynomial time ultrapowers and the consistency of circuit lower bounds

Cites work

• scientific article; zbMATH DE number 3557241 (Why is no real title available?)
• scientific article; zbMATH DE number 3305097 (Why is no real title available?)
• Algebrization: a new barrier in complexity theory
• Approximate counting by hashing in bounded arithmetic
• Approximate counting in bounded arithmetic
• Bounded arithmetic and the polynomial hierarchy
• Circuit lower bounds in bounded arithmetics
• Consequences of the provability of NP ⊆ P/poly
• Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic
• Natural proofs
• On the scheme of induction for bounded arithmetic formulas
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic

Cited in

(5)

• Feasibly constructive proofs of succinct weak circuit lower bounds
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• Polynomial time ultrapowers and the consistency of circuit lower bounds
• Indistinguishability obfuscation, range avoidance, and bounded arithmetic
• Unprovability of strong complexity lower bounds in bounded arithmetic

This page was built for publication: Unprovability of circuit upper bounds in Cook's theory PV

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