Strong isomorphism reductions in complexity theory
Buss, Samuel R.
Chen, Yijia
Flum, Jörg
Friedman, Sy D.
Müller, Moritz
Centre de Recerca Matemàtica

Publicació: Centre de Recerca Matemàtica 2011
Descripció: 26 p.
Resum: 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.
Drets: Aquest document està subjecte a una llicència d'ús de Creative Commons, amb la qual es permet copiar, distribuir i comunicar públicament l'obra sempre que se'n citin l'autor original, la universitat i el centre i no se'n faci cap ús comercial ni obra derivada, tal com queda estipulat en la llicència d'ús Creative Commons
Llengua: Anglès
Col·lecció: Centre de Recerca Matemàtica. Prepublicacions
Col·lecció: Prepublicacions del Centre de Recerca Matemàtica ; 1009
Document: Article ; Prepublicació ; Versió de l'autor
Matèria: Lògica matemàtica ; Complexitat computacional



26 p, 265.7 KB

El registre apareix a les col·leccions:
Documents de recerca > Prepublicacions

 Registre creat el 2011-09-10, darrera modificació el 2023-02-11



   Favorit i Compartir