Feasible graphs with standard universe (Q1295403)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Feasible graphs with standard universe |
scientific article |
Statements
Feasible graphs with standard universe (English)
0 references
14 June 2000
0 references
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.
0 references
recursive graphs
0 references
p-time models
0 references
computable trees
0 references
isomorphism problem
0 references
recursive isomorphism
0 references
recursive tree
0 references
recursive equivalence relation
0 references