Relating the bounded arithmetic and polynomial time hierarchies
type: Item
instance of: scholarly article
title: Relating the bounded arithmetic and polynomial time hierarchies
zbMATH Open document ID: 0829.03035
DOI: 10.1016/0168-0072(94)00057-A
author: Samuel R. Buss
published in: Annals of Pure and Applied Logic
publication date: 1995-10-04T00:00:00Z
Mathematics Subject Classification ID: 03F30
zbMATH DE Number: 802548
zbMATH Keywords: finite axiomatizability
zbMATH Keywords: bounded arithmetic
zbMATH Keywords: polynomial time hierarchy
MaRDI profile type: Publication
cites work: Q4325772
cites work: Q3800030
cites work: Q3476809
cites work: On truth-table reducibility to SAT
cites work: An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
cites work: Q3999199
cites work: Turing machines that take advice
cites work: Q4010360
cites work: Fragments of Bounded Arithmetic and Bounded Query Classes
cites work: Bounded arithmetic and the polynomial hierarchy
cites work: Existence and feasibility in arithmetic
cites work: Q4010368
cites work: Q3487339
cites work: On the scheme of induction for bounded arithmetic formulas
cites work: Notes on polynomially bounded arithmetic
Wikidata QID: Q126372038
Recommended article: Bounded arithmetic and the polynomial hierarchy
Recommended article: Q4850554
Recommended article: Q4266170
Recommended article: On relativized nondeterministic polynomial-time bounded computations
Recommended article: Q2753676
Recommended article: A time-space hierarchy between polynomial time and polynomial space
Recommended article: Notes on polynomially bounded arithmetic
Recommended article: Some hierarchies of relativized time-bounded complexity classes
Recommended article: Q3472100
Recommended article: Q3800030
description: scientific article; zbMATH DE number 802548