Multifunction algebras and the provability of PH

DOI10.1016/S0168-0072(00)00015-4zbMATH Open0959.03049MaRDI QIDQ1577486FDOQ1577486

Authors: Chris Pollett 

Publication date: 2 May 2001

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

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

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)

Cites Work

• Title not available (Why is that?)
• Existence and feasibility in arithmetic
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• Title not available (Why is that?)
• An arithmetical characterization of NP
• Structure and definability in general bounded arithmetic theories
• Title not available (Why is that?)
• A Model-Theoretic Property of Sharply Bounded Formulae, with some Applications
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Title not available (Why is that?)
• Provability of the pigeonhole principle and the existence of infinitely many primes
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (8)

• Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\)
• 2000 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium 2000. La Sorbonne, Paris, France, July 23-31, 2000
• The strength of sharply bounded induction requires MSP
• 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)