Multifunction algebras and the provability of \(PH\downarrow\)
From MaRDI portal
Publication:1577486
DOI10.1016/S0168-0072(00)00015-4zbMath0959.03049MaRDI QIDQ1577486
Publication date: 2 May 2001
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
bounded arithmetic; polynomial hierarchy; independence results; complexity theory; conservation results; multifunction algebras
03F30: First-order arithmetic and fragments
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
On the finite axiomatizability of, Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\), The strength of sharply bounded induction requires MSP, Independence results for variants of sharply bounded induction, New models of bounded induction axioms, \(S_{k,\text{exp}}\) does not prove \(\text{NP} = \text{co-NP}\) uniformly, 2000 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium 2000, The polynomial and linear hierarchies in models where the weak pigeonhole principle fails
Cites Work
- Structure and definability in general bounded arithmetic theories
- An arithmetical characterization of NP
- The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Provability of the pigeonhole principle and the existence of infinitely many primes
- A Model-Theoretic Property of Sharply Bounded Formulae, with some Applications
- Existence and feasibility in arithmetic
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
