Multifunction algebras and the provability of \(PH\downarrow\)

DOI10.1016/S0168-0072(00)00015-4zbMath0959.03049MaRDI QIDQ1577486

Chris Pollett

Publication date: 2 May 2001

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

bounded arithmeticpolynomial hierarchyindependence resultscomplexity theoryconservation resultsmultifunction algebras

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (8)

The polynomial and linear hierarchies in models where the weak pigeonhole principle fails ⋮ On the finite axiomatizability of ⋮ The strength of sharply bounded induction requires MSP ⋮ 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 ⋮ Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\) ⋮ Independence results for variants of sharply bounded induction

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Multifunction algebras and the provability of \(PH\downarrow\)