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 |
Mark as duplicate
Export citation
Request removal from index
|
Download options
References found in this work BETA
Every Recursive Linear Ordering has a Copy in Dtime-Space (N, Log(N)).Serge Grigorieff - 1990 - Journal of Symbolic Logic 55 (1):260-276.
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.
Citations of this work BETA
No citations found.
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.
Almost Everywhere Elimination of Probability Quantifiers.H. Jerome Keisler & Wafik Boulos Lotfallah - 2009 - Journal of Symbolic Logic 74 (4):1121 - 1142.
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.
Game-Theoretical Semantics for Peirce's Existential Graphs.Robert W. Burch - 1994 - Synthese 99 (3):361 - 375.
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 )
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
