Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-17T13:33:31.099Z Has data issue: false hasContentIssue false

Strong isomorphism reductions in complexity theory

Published online by Cambridge University Press:  12 March 2014

Sam Buss
Affiliation:
Department of Mathematics, University of California, San Diego, La Jolla, California 92093-0112, USA, E-mail: sbuss@math.ucsd.edu
Yijia Chen
Affiliation:
Basic Studies in Computing Science (Basics), Department of Computer Science, Shanghai Jiaotong University, Shanghai 200030, China, E-mail: yijia.chen@cs.sjtu.edu.cn
Jörg Flum
Affiliation:
Mathematisches Institut, Albert-Ludwigs Universität Freiburg, 79104 Freiburg, Germany, E-mail: joerg.flum@math.uni-freiburg.de
Sy-David Friedman
Affiliation:
Kurt Gödel Research Center, Währinger Straße 25, A-1090 Wien, Austria, E-mail: sdf@logic.univie.ac.at
Moritz Müller
Affiliation:
Centre de Recerca Matemàtica, Campus Bellaterra, Edifici C, 08193 Bellaterra (Barcelona), Spain, E-mail: mmueller@crm.cat

Abstract

We give the first systematic study of strong isomorphism reductions, a notion of reduction more appropriate than polynomial time reduction when, for example, comparing the computational complexity of the isomorphim problem for different classes of structures. We show that the partial ordering of its degrees is quite rich. We analyze its relationship to a further type of reduction between classes of structures based on purely comparing for every n the number of nonisomorphic structures of cardinality at most n in both classes. Furthermore, in a more general setting we address the question of the existence of a maximal element in the partial ordering of the degrees.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable