Unprovability of circuit upper bounds in Cook's theory PV

DOI10.23638/LMCS-13(1:4)2017zbMATH Open1448.03048arXiv1605.00263MaRDI QIDQ2980966FDOQ2980966

Authors: Jan Krajíček, Igor C. Oliveira 

Publication date: 8 May 2017

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

• On the scheme of induction for bounded arithmetic formulas
• Title not available (Why is that?)
• Natural proofs
• Algebrization: a new barrier in complexity theory
• Title not available (Why is that?)
• Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
• Consequences of the provability of NP ⊆ P/poly
• Bounded arithmetic and the polynomial hierarchy
• Circuit lower bounds in bounded arithmetics
• Approximate counting in bounded arithmetic
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Approximate counting by hashing in bounded arithmetic
• Logical strength of complexity theory and a formalization of the PCP theorem in 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)