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

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
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/0168-0072(91)90008-a
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 69,979
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

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

Citations of this work BETA

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 8 citations / Add more citations

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 index
2014-01-16

Total views
13 ( #768,750 of 2,505,145 )

Recent downloads (6 months)
2 ( #277,142 of 2,505,145 )

How can I increase my downloads?

Downloads

My notes