Polynomial-time versus recursive models

Annals of Pure and Applied Logic 54 (1):17-58 (1991)
  Copy   BIBTEX

Abstract

The central problem considered in this paper is whether a given recursive structure is recursively isomorphic to a polynomial-time structure. Positive results are obtained for all relational structures, for all Boolean algebras and for the natural numbers with addition, multiplication and the unary function 2x. Counterexamples are constructed for recursive structures with one unary function and for Abelian groups and also for relational structures when the universe of the structure is fixed. Results are also given which distinguish primitive recursive structures, exponential-time structures and structures with honest witnesses

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,593

External links

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

Through your library

Similar books and articles

Polynomial-time abelian groups.Douglas Cenzer & Jeffrey Remmel - 1992 - Annals of Pure and Applied Logic 56 (1-3):313-363.
Weak Cardinality Theorems.Till Tantau - 2005 - Journal of Symbolic Logic 70 (3):861 - 878.
A Note on Recursive Models of Set Theories.Domenico Zambella & Antonella Mancini - 2001 - Notre Dame Journal of Formal Logic 42 (2):109-115.
Complexity, Decidability and Completeness.Douglas Cenzer & Jeffrey B. Remmel - 2006 - Journal of Symbolic Logic 71 (2):399 - 424.
Light affine lambda calculus and polynomial time strong normalization.Kazushige Terui - 2007 - Archive for Mathematical Logic 46 (3-4):253-280.
On Nondeterminism, Enumeration Reducibility and Polynomial Bounds.Kate Copestake - 1997 - Mathematical Logic Quarterly 43 (3):287-310.
On Splitting of a Recursive Set with Polynomial Time Minimal Pairs.Chen Zhixiang - 1989 - Mathematical Logic Quarterly 35 (5):423-432.
Machines Over the Reals and Non‐Uniformity.Felipe Cucker - 1997 - Mathematical Logic Quarterly 43 (2):143-157.
Inhomogeneity of the p-s-Degrees of Recursive Functions.Asae Mochizuki & Juichi Shinoda - 2000 - Mathematical Logic Quarterly 46 (3):385-392.
Feasible Graphs and Colorings.Douglas Cenzer & Jeffrey Remmel - 1995 - Mathematical Logic Quarterly 41 (3):327-352.
Polynomial time operations in explicit mathematics.Thomas Strahm - 1997 - Journal of Symbolic Logic 62 (2):575-594.
The Analytic Polynomial-Time Hierarchy.Herbert Baier & Klaus W. Wagner - 1998 - Mathematical Logic Quarterly 44 (4):529-544.

Analytics

Added to PP
2014-01-16

Downloads
16 (#774,541)

6 months
2 (#668,348)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Polynomial-time abelian groups.Douglas Cenzer & Jeffrey Remmel - 1992 - Annals of Pure and Applied Logic 56 (1-3):313-363.
Space complexity of Abelian groups.Douglas Cenzer, Rodney G. Downey, Jeffrey B. Remmel & Zia Uddin - 2009 - Archive for Mathematical Logic 48 (1):115-140.
Feasible Graphs and Colorings.Douglas Cenzer & Jeffrey Remmel - 1995 - Mathematical Logic Quarterly 41 (3):327-352.

View all 9 citations / Add more citations

References found in this work

Complexity-theoretic algebra II: Boolean algebras.A. Nerode & J. B. Remmel - 1989 - Annals of Pure and Applied Logic 44 (1-2):71-99.

Add more references