Strong isomorphism reductions in complexity theory

DOI10.2178/jsl/1318338855zbMath1248.03060OpenAlexW1967481203MaRDI QIDQ3107360

Yijia Chen, Moritz Müller, Jörg Flum, Samuel R. Buss, Sy-David Friedman

Publication date: 23 December 2011

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.190.342

zbMATH Keywords

complexity classesisomorphism problems

Mathematics Subject Classification ID

Constructive and recursive analysis (03F60) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Metamathematics of constructive systems (03F50)

Related Items (6)

A Parameterized Halting Problem ⋮ Primitive recursive equivalence relations and their primitive recursive complexity ⋮ COMPLEXITY OF EQUIVALENCE RELATIONS AND PREORDERS FROM COMPUTABILITY THEORY ⋮ Reducibilities among equivalence relations induced by recursively enumerable structures ⋮ On Borel complexity of the isomorphism problems for graph related classes of Lie algebras and finite p-groups ⋮ Graphs realised by r.e. equivalence relations

This page was built for publication: Strong isomorphism reductions in complexity theory