Multifunction algebras and the provability of \(PH\downarrow\)
type: Item
instance of: scholarly article
title: Multifunction algebras and the provability of \(PH\downarrow\)
zbMATH Open document ID: 0959.03049
DOI: 10.1016/S0168-0072(00)00015-4
author: Chris Pollett
published in: Annals of Pure and Applied Logic
publication date: 2001-05-02T00:00:00Z
Mathematics Subject Classification ID: 03F30
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1501509
zbMATH Keywords: complexity theory
zbMATH Keywords: conservation results
zbMATH Keywords: multifunction algebras
zbMATH Keywords: independence results
zbMATH Keywords: bounded arithmetic
zbMATH Keywords: polynomial hierarchy
MaRDI profile type: Publication
cites work: Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
cites work: Q3794177
cites work: Q4282609
cites work: A Model-Theoretic Property of Sharply Bounded Formulae, with some Applications
cites work: The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
cites work: An arithmetical characterization of NP
cites work: Existence and feasibility in arithmetic
cites work: Provability of the pigeonhole principle and the existence of infinitely many primes
cites work: Structure and definability in general bounded arithmetic theories
cites work: Q4281694
cites work: Q4850554
cites work: Q3487339
cites work: Q3140644
description: scientific article; zbMATH DE number 1501509