Loquacious highness characterization of isomorphism completeness for classes of structures

Let KK be a class of structures. A degree is loquaciously high for isomorphism for KK if it computes, uniformly from any pair of structures in KK, functions that are inverse isomorphisms whenever the structures are isomorphic. A degree is uniformly high for isomorphism for KK if it computes, uniformly from any pair of isomorphic structures in KK, an isomorphism between them. The isomorphism problem for KK is the set of pairs of structures in KK that are isomorphic.

Loquacious highness characterization. If every degree loquaciously high for isomorphism for KK is uniformly high for isomorphism, then the isomorphism problem for KK is Σ11\Sigma^1_1-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 Σ11\Sigma^1_1-completeness, loquacious highness implies uniform highness together with enumeration of Kleene's O\mathcal{O}, 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.