Applicative theories for the polynomial hierarchy of time and its levels

&
Annals of Pure and Applied Logic 164 (6):663-675 (2013)
  Copy   BIBTEX

Abstract

In this paper we introduce applicative theories which characterize the polynomial hierarchy of time and its levels. These theories are based on a characterization of the functions in the polynomial hierarchy using monotonicity constraints, introduced by Ben-Amram, Loff, and Oitavem

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2012.05.006

Links

PhilArchive



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

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

Polynomial time operations in explicit mathematics.Thomas Strahm - 1997 - Journal of Symbolic Logic 62 (2):575-594.
Truth in applicative theories.Reinhard Kahle - 2001 - Studia Logica 68 (1):103-128.
N \hbox{\sf n} -strictness in applicative theories.Reinhard Kahle - 2000 - Archive for Mathematical Logic 39 (2):125-144.
Machines Over the Reals and Non‐Uniformity.Felipe Cucker - 1997 - Mathematical Logic Quarterly 43 (2):143-157.
Review: Thomas Strahm, Polynomial Time Operations in Explicit Mathematics ; Andrea Cantini, Feasible Operations and Applicative Theories Based on $\lambda \eta $. [REVIEW]Fernando Ferreira - 2002 - Bulletin of Symbolic Logic 8 (4):534-535.
The Analytic Polynomial-Time Hierarchy.Herbert Baier & Klaus W. Wagner - 1998 - Mathematical Logic Quarterly 44 (4):529-544.
The polynomial hierarchy for some structures over the binary words.Herwig Nübling - 2007 - Mathematical Logic Quarterly 53 (1):43-51.
Consequences of the Provability of NP ⊆ P/poly.Stephen Cook & Jan Krajíček - 2007 - Journal of Symbolic Logic 72 (4):1353 - 1371.
Admissible closures of polynomial time computable arithmetic.Dieter Probst & Thomas Strahm - 2011 - Archive for Mathematical Logic 50 (5):643-660.
On polynomial time computation over unordered structures.Andreas Blass, Yuri Gurevich & Saharon Shelah - 2002 - Journal of Symbolic Logic 67 (3):1093-1125.
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.
Three obstructions: Forms of causation, chronotopoids, and levels of reality.Roberto Poli - 2007 - Axiomathes 17 (1):1-18.
A theory of rules for enumerated classes of functions.Andreas Schlüter - 1995 - Archive for Mathematical Logic 34 (1):47-63.

Analytics

Added to PP
2013-12-12

Downloads
28 (#568,347)

6 months
9 (#304,685)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Reinhard Kahle
University Tübingen

Citations of this work

Add more citations

References found in this work

Totality in applicative theories.Gerhard Jäger & Thomas Strahm - 1995 - Annals of Pure and Applied Logic 74 (2):105-120.
Foundations of Constructive Mathematics.Michael J. Beeson - 1987 - Studia Logica 46 (4):398-399.
The provably terminating operations of the subsystem of explicit mathematics.Dieter Probst - 2011 - Annals of Pure and Applied Logic 162 (11):934-947.
Elementary explicit types and polynomial time operations.Daria Spescha & Thomas Strahm - 2009 - Mathematical Logic Quarterly 55 (3):245-258.

View all 12 references / Add more references