On the unprovability of circuit size bounds in intuitionistic S^1_2
From MaRDI portal
Publication:6925609
Cites work
- A new method for establishing conservativity of classical systems over their intuitionistic version
- Applied Proof Theory: Proof Interpretations and Their Use in Mathematics
- Circuit lower bounds in bounded arithmetics
- Computational Complexity
- Consequences of the provability of NP ⊆ P/poly
- Consistency of circuit lower bounds with bounded theories
- Extracting Algorithms from Intuitionistic Proofs
- Functional interpretations of feasibly constructive arithmetic
- Handbook of proof theory
- scientific article; zbMATH DE number 4059391 (Why is no real title available?)
- scientific article; zbMATH DE number 4066875 (Why is no real title available?)
- scientific article; zbMATH DE number 176198 (Why is no real title available?)
- scientific article; zbMATH DE number 1354169 (Why is no real title available?)
- scientific article; zbMATH DE number 1070621 (Why is no real title available?)
- If NP languages are hard on the worst-case, then it is easy to find their hard instances
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Interpreting classical theories in constructive ones
- Natural proofs
- On the Consistency of Circuit Lower Bounds for Non-Deterministic Time
- On the Hierarchy of Intuitionistic Bounded Arithmetic
- ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
- On uniformity and circuit lower bounds
- Polynomial time ultrapowers and the consistency of circuit lower bounds
- Proof complexity of intuitionistic implicational formulas
- Provably total functions of intuitionistic bounded arithmetic
- Pseudodeterministic constructions in subexponential time
- Strong co-nondeterministic lower bounds for NP cannot be proved feasibly
- Unprovability of circuit upper bounds in Cook's theory PV
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
- Unprovability of strong complexity lower bounds in bounded arithmetic
This page was built for publication: On the unprovability of circuit size bounds in intuitionistic \(\mathsf{S}^1_2\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6925609)
