Unprovability of circuit upper bounds in Cook's theory PV
From MaRDI portal
Publication:2980966
DOI10.23638/LMCS-13(1:4)2017zbMath1448.03048arXiv1605.00263MaRDI QIDQ2980966
Jan Krajíček, Igor C. Oliveira
Publication date: 8 May 2017
Full work available at URL: https://arxiv.org/abs/1605.00263
Analysis of algorithms and problem complexity (68Q25) First-order arithmetic and fragments (03F30) Complexity of proofs (03F20)
Related Items (2)
Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ Polynomial time ultrapowers and the consistency of circuit lower bounds
Cites Work
- Unnamed Item
- Unnamed Item
- Circuit lower bounds in bounded arithmetics
- On the scheme of induction for bounded arithmetic formulas
- Bounded arithmetic and the polynomial hierarchy
- Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic
- Algebrization
- Approximate counting by hashing in bounded arithmetic
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
- Approximate counting in bounded arithmetic
- Consequences of the provability of NP ⊆ P/poly
- Natural proofs
This page was built for publication: Unprovability of circuit upper bounds in Cook's theory PV
