Annals of Pure and Applied Logic 94 (1-3):21-35 (1998)

Abstract
A computable graph is constructed which is not computably isomorphic to any polynomial-time graph with a standard universe . Conditions are given under which a computable graph is computably isomorphic to a polynomial-time graph with a standard universe — for example, if every vertex has finite degree. Two special types of graphs are studied. It is shown that any computable tree is recursively isomorphic to a p-time tree with standard universe and that any computable equivalence relation is computably isomorphic to a p-time equivalence relation with standard universe
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/s0168-0072(97)00064-x
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,114
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

Polynomial-Time Abelian Groups.Douglas Cenzer & Jeffrey Remmel - 1992 - Annals of Pure and Applied Logic 56 (1-3):313-363.
Polynomial-Time Versus Recursive Models.Douglas Cenzer & Jeffrey Remmel - 1991 - Annals of Pure and Applied Logic 54 (1):17-58.
Complexity-Theoretic Algebra II: Boolean Algebras.A. Nerode & J. B. Remmel - 1989 - Annals of Pure and Applied Logic 44 (1-2):71-99.
Feasible Graphs and Colorings.Douglas Cenzer & Jeffrey Remmel - 1995 - Mathematical Logic Quarterly 41 (3):327-352.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Feasible Graphs and Colorings.Douglas Cenzer & Jeffrey Remmel - 1995 - Mathematical Logic Quarterly 41 (3):327-352.
Graphs with ∏ 1 0 (K)Y-Sections.Boško Živaljević - 1993 - Archive for Mathematical Logic 32 (4):259-273.
A Natural Explanation of the Existence and Laws of Our Universe.Quentin Smith - 1990 - Australasian Journal of Philosophy 68 (1):22 – 43.
Expansions of Ultrahomogeneous Graphs.J. E. Helmreich - 1995 - Notre Dame Journal of Formal Logic 36 (3):414-424.
Small Universal Families for Graphs Omitting Cliques Without GCH.Katherine Thompson - 2010 - Archive for Mathematical Logic 49 (7-8):799-811.
Standard Sets in Nonstandard Set Theory.Petr Andreev & Karel Hrbacek - 2004 - Journal of Symbolic Logic 69 (1):165-182.
.Jay Zeman - unknown
Space Complexity of Abelian Groups.Douglas Cenzer, Rodney G. Downey, Jeffrey B. Remmel & Zia Uddin - 2009 - Archive for Mathematical Logic 48 (1):115-140.

Analytics

Added to PP index
2014-01-16

Total views
13 ( #766,098 of 2,499,265 )

Recent downloads (6 months)
1 ( #418,195 of 2,499,265 )

How can I increase my downloads?

Downloads

My notes