Feasible graphs with standard universe (Q1295403)

In the paper under review the authors study the isomorphism problem for recursive graphs. It follows easily from well-known work by Grigorieff that any recursive graph is recursively isomorphic to a p-time structure. The authors proved in a previous paper that there is a p-time directed graph which is not recursively isomorphic to any p-time directed graph with standard universe. In this paper the authors study structural properties of graphs which ensure the existence of a recursive isomorphism with a p-time model having a standard universe. Examples of simple graphs which are not recursively isomorphic to a p-time graph with standard universe are constructed. Conditions are given under which a computable graph is recursively isomorphic to a polynomial-time graph with standard universe. It is shown that any recursive tree is recursively isomorphic to a p-time tree with standard universe and that any recursive equivalence relation is recursively isomorphic to a p-time equivalence relation with standard universe.