Strong isomorphism reductions in complexity theory

DOI10.2178/JSL/1318338855MaRDI QIDQ3107360zbMATH OpenOpenAlexFDO

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

Publication date 23 December 2011

Published in 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

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

Recommendations

• Reductions among polynomial isomorphism types
• Isomorphism relations on computable structures
• Reductions to Graph Isomorphism
• On the isomorphism conjecture for weak reducibilities
• On the complexity-relativized strong reducibilities

Cited in

(11)

• On the isomorphism conjecture for weak reducibilities
• Barendregt's problem \#26 and combinatory strong reduction
• Graphs realised by r.e. equivalence relations
• A Parameterized Halting Problem
• Complexity of equivalence relations and preorders from computability theory
• scientific article; zbMATH DE number 176750 (Why is no real title available?)
• 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
• STRUCTURAL HIGHNESS NOTIONS
• Strong polynomial-time reducibility
• Reducibilities among equivalence relations induced by recursively enumerable structures

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3107360)