Strong isomorphism reductions in complexity theory
From MaRDI portal
Publication:3107360
DOI10.2178/jsl/1318338855zbMath1248.03060MaRDI 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
03F60: Constructive and recursive analysis
03D15: Complexity of computation (including implicit computational complexity)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
03F50: Metamathematics of constructive systems
Related Items
On Borel complexity of the isomorphism problems for graph related classes of Lie algebras and finite p-groups, Primitive recursive equivalence relations and their primitive recursive complexity, Reducibilities among equivalence relations induced by recursively enumerable structures, Graphs realised by r.e. equivalence relations, A Parameterized Halting Problem, COMPLEXITY OF EQUIVALENCE RELATIONS AND PREORDERS FROM COMPUTABILITY THEORY