Multifunction algebras and the provability of PH

DOI10.1016/S0168-0072(00)00015-4MaRDI QIDQ1577486zbMATH OpenFDO

Authors Chris Pollett

Publication date 2 May 2001

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

zbMATH Keywords

complexity theorybounded arithmeticpolynomial hierarchyindependence resultsconservation resultsmultifunction algebras

Mathematics Subject Classification ID

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

Recommendations

• Relating the bounded arithmetic and polynomial time hierarchies
• Bounded arithmetic and the polynomial hierarchy
• scientific article; zbMATH DE number 4059391
• Consequences of the provability of NP ⊆ P/poly

Cites work

• scientific article; zbMATH DE number 440487 (Why is no real title available?)
• scientific article; zbMATH DE number 4160722 (Why is no real title available?)
• scientific article; zbMATH DE number 4059391 (Why is no real title available?)
• scientific article; zbMATH DE number 512985 (Why is no real title available?)
• scientific article; zbMATH DE number 517079 (Why is no real title available?)
• scientific article; zbMATH DE number 806753 (Why is no real title available?)
• A Model-Theoretic Property of Sharply Bounded Formulae, with some Applications
• An arithmetical characterization of NP
• Existence and feasibility in arithmetic
• Provability of the pigeonhole principle and the existence of infinitely many primes
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Structure and definability in general bounded arithmetic theories
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses

Cited in

(8)

• Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\)
• The strength of sharply bounded induction requires MSP
• 2000 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium 2000. La Sorbonne, Paris, France, July 23-31, 2000
• On the finite axiomatizability of \(\forall\hat{\Sigma}^{\mathrm{b}}_1 (\hat{\mathsf{R}}^1_2)\)
• The polynomial and linear hierarchies in models where the weak pigeonhole principle fails
• Independence results for variants of sharply bounded induction
• \(S_{k,\text{exp}}\) does not prove \(\text{NP} = \text{co-NP}\) uniformly
• New models of bounded induction axioms

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1577486)