The polynomial hierarchy for some structures over the binary words

Mathematical Logic Quarterly 53 (1):43-51 (2007)
  Copy   BIBTEX

Abstract

For each k > 0 we construct an algebraic structure over which the polynomial hierarchy collapses at level k. We also find an algebraic structure over which the polynomial hierarchy does not collapse

Categories

Keywords

Reprint years

DOI

10.1002/malq.200610025

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,139

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

The polynomial and linear hierarchies in models where the weak pigeonhole principle fails.Leszek Aleksander Kołodziejczyk & Neil Thapen - 2008 - Journal of Symbolic Logic 73 (2):578-592.
Consequences of the Provability of NP ⊆ P/poly.Stephen Cook & Jan Krajíček - 2007 - Journal of Symbolic Logic 72 (4):1353 - 1371.
On two questions about feasibly constructive arithmetic.Morteza Moniri - 2003 - Mathematical Logic Quarterly 49 (4):425.
Machines Over the Reals and Non‐Uniformity.Felipe Cucker - 1997 - Mathematical Logic Quarterly 43 (2):143-157.
Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic.Arnold Beckmann & Samuel R. Buss - 2009 - Journal of Mathematical Logic 9 (1):103-138.
The Analytic Polynomial-Time Hierarchy.Herbert Baier & Klaus W. Wagner - 1998 - Mathematical Logic Quarterly 44 (4):529-544.
Polynomial time operations in explicit mathematics.Thomas Strahm - 1997 - Journal of Symbolic Logic 62 (2):575-594.
Admissible closures of polynomial time computable arithmetic.Dieter Probst & Thomas Strahm - 2011 - Archive for Mathematical Logic 50 (5):643-660.
Review: Jan Krajicek, Pavel Pudlak, Gaisi Takeuti, Bounded Arithmetic and the Polynomial Hierarchy; Samuel R. Buss, Relating the Bounded Arithmetic and Polynomial Time Hierarchies; Domenico Zambella, Notes on Polynomially Bounded Arithmetic. [REVIEW]Stephen Cook - 1999 - Journal of Symbolic Logic 64 (4):1821-1823.
On polynomial time computation over unordered structures.Andreas Blass, Yuri Gurevich & Saharon Shelah - 2002 - Journal of Symbolic Logic 67 (3):1093-1125.
Preservation theorems for bounded formulas.Morteza Moniri - 2007 - Archive for Mathematical Logic 46 (1):9-14.
Separations and transfers in the polynomial hierarchy of infinite abelian groups.M. Bourgade - 2001 - Mathematical Logic Quarterly 47 (4):493-502.
The algebraic structure of the isomorphic types of tally, polynomial time computable sets.Yongge Wang - 2002 - Archive for Mathematical Logic 41 (3):215-244.
An Analysis of the W -Hierarchy.Yijia Chen, Jörg Flum & Martin Grohe - 2007 - Journal of Symbolic Logic 72 (2):513 - 534.

Analytics

Added to PP
2014-01-16

Downloads
9 (#1,154,504)

6 months
2 (#1,015,942)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references