Relating the bounded arithmetic and polynomial time hierarchies
From MaRDI portal
Recommendations
- Bounded arithmetic and the polynomial hierarchy
- scientific article; zbMATH DE number 806753
- scientific article; zbMATH DE number 1344922
- On relativized nondeterministic polynomial-time bounded computations
- scientific article; zbMATH DE number 1670480
- A time-space hierarchy between polynomial time and polynomial space
- Notes on polynomially bounded arithmetic
- Some hierarchies of relativized time-bounded complexity classes
- scientific article; zbMATH DE number 4139739
- scientific article; zbMATH DE number 4066875
Cites work
- An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
- Bounded arithmetic and the polynomial hierarchy
- Existence and feasibility in arithmetic
- Fragments of Bounded Arithmetic and Bounded Query Classes
- scientific article; zbMATH DE number 4145897 (Why is no real title available?)
- scientific article; zbMATH DE number 4160722 (Why is no real title available?)
- scientific article; zbMATH DE number 4066875 (Why is no real title available?)
- scientific article; zbMATH DE number 48150 (Why is no real title available?)
- scientific article; zbMATH DE number 65749 (Why is no real title available?)
- scientific article; zbMATH DE number 65757 (Why is no real title available?)
- scientific article; zbMATH DE number 733384 (Why is no real title available?)
- Notes on polynomially bounded arithmetic
- On the scheme of induction for bounded arithmetic formulas
- On truth-table reducibility to SAT
- Turing machines that take advice
Cited in
(30)- Bounded arithmetic and the polynomial hierarchy
- More on BPP and the polynomial-time hierarchy
- End extensions of models of linearly bounded arithmetic
- A second-order system for polytime reasoning based on Grädel's theorem.
- Multifunction algebras and the provability of PH
- A model-theoretic characterization of the weak pigeonhole principle
- Induction rules in bounded arithmetic
- Separations of first and second order theories in bounded arithmetic
- 2000 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium 2000. La Sorbonne, Paris, France, July 23-31, 2000
- Truth definitions without exponentiation and the \(\Sigma _{1}\) collection scheme
- The polynomial and linear time hierarchies in V0
- Approximate counting by hashing in bounded arithmetic
- On the Hierarchy of Intuitionistic Bounded Arithmetic
- A note on the \(\Sigma_1\) collection scheme and fragments of bounded arithmetic
- Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic
- On the correspondence between arithmetic theories and propositional proof systems – a survey
- Strengths and Weaknesses of LH Arithmetic
- On the finite axiomatizability of \(\forall\hat{\Sigma}^{\mathrm{b}}_1 (\hat{\mathsf{R}}^1_2)\)
- Approximate counting in bounded arithmetic
- The Polynomial and Linear Hierarchies in V0
- Consequences of the provability of NP ⊆ P/poly
- Notes on polynomially bounded arithmetic
- A model of \(\widehat{R}^2_3\) inside a subexponential time resource
- Preservation theorems and restricted consistency statements in bounded arithmetic
- On parallel hierarchies and R ki
- On Herbrand's theorem
- Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
- Unprovability of strong complexity lower bounds in bounded arithmetic
- From proof complexity to circuit complexity via interactive protocols
- On proving consistency of equational theories in bounded arithmetic
This page was built for publication: Relating the bounded arithmetic and polynomial time hierarchies
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1899144)
