The computable embedding problem |
| |
Authors: | J Carson E Fokina V S Harizanov J F Knight S Quinn C Safranski J Wallbaum |
| |
Institution: | 1. Kurt G?del Res. Center Math. Log., Univ. Vienna, Waehringerstrasse 25, 1090, Vienna, Austria 2. Dep. Math., George Washington Univ., 2115 G St. NW, Washington D.C., 20052, USA 3. Dep. Math., Univ. Notre Dame, 255 Hurley, Notre Dame, IN, 46556, USA 4. Dep. Math., Dominican Univ., 7900 W Division Street, River Forest, IL, 60305, USA 5. Saint Vincent College, 300 Fraser Purchase Road, Latrobe, PA, 15650-2690, USA
|
| |
Abstract: | Calvert calculated the complexity of the computable isomorphism problem for a number of familiar classes of structures. Rosendal
suggested that it might be interesting to do the same for the computable embedding problem. By the computable isomorphism
problem and (computable embedding problem) we mean the difficulty of determining whether there exists an isomorphism (embedding)
between two members of a class of computable structures. For some classes, such as the class of
\mathbbQ \mathbb{Q} -vector spaces and the class of linear orderings, it turns out that the two problems have the same complexity. Moreover, calculations
are essentially the same. For other classes, there are differences. We present examples in which the embedding problem is
trivial (within the class) and the computable isomorphism problem is more complicated. We also give an example in which the
embedding problem is more complicated than the isomorphism problem. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|