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

From MaRDI portal

Jump to:navigation, search

scientific article

In more languages

Language	Label	Description	Also known as
English	Multifunction algebras and the provability of \(PH\downarrow\)	scientific article

Statements

scholarly article

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

Annals of Pure and Applied Logic

publication date

2 May 2001

zbMATH Keywords

complexity theory

conservation results

multifunction algebras

independence results

bounded arithmetic

polynomial hierarchy

MaRDI profile type

MaRDI publication profile

Relative to a Random Oracle<i>A</i>, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1

A Model-Theoretic Property of Sharply Bounded Formulae, with some Applications

The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses

An arithmetical characterization of NP

Existence and feasibility in arithmetic

Provability of the pigeonhole principle and the existence of infinitely many primes

Structure and definability in general bounded arithmetic theories

Identifiers

zbMATH Open document ID

10.1016/S0168-0072(00)00015-4

Mathematics Subject Classification ID

zbMATH DE Number

Sitelinks

Mathematics(1 entry)

mardi Publication:1577486

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q1577486&oldid=34251999"