Loquacious highness characterization of isomorphism completeness for classes of structures
Loquacious highness characterization of isomorphism completeness for classes of structures
Let be a class of structures. A degree is loquaciously high for isomorphism for if it computes, uniformly from any pair of structures in , functions that are inverse isomorphisms whenever the structures are isomorphic. A degree is uniformly high for isomorphism for if it computes, uniformly from any pair of isomorphic structures in , an isomorphism between them. The isomorphism problem for is the set of pairs of structures in that are isomorphic.
Loquacious highness characterization. If every degree loquaciously high for isomorphism for is uniformly high for isomorphism, then the isomorphism problem for is -complete.
This is posed as an open problem concerning the relationship between structural highness notions and the complexity of isomorphism problems. The statement is related to the preceding results showing that, under -completeness, loquacious highness implies uniform highness together with enumeration of Kleene's , but the converse characterization remains open.
Sources & referencesView supporting material
Primary source
Wesley Calvert, Johanna N. Y. Franklin and Dan Turetsky, “Failure Modes for Structural Highness Notions”, arXiv:2503.13727 (2025).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.