The cardinal-inequality realization conjecture for cotimescotimes graphs

An algorithm is a procedure that takes an input and may terminate or run forever, and xx is an input to such an algorithm. A \otimes graph with cardinal inequalities is a \otimes graph G\mathcal{G} equipped with cardinal inequalities between its vertices; it is realizable when it has a model satisfying those constraints.

Cardinal-inequality realization conjecture. For every algorithm A\mathcal{A} and input xx, there exists a \otimes graph G\mathcal{G} with cardinal inequalities such that

A terminates on xG is realizable.\mathcal{A}\text{ terminates on }x \quad\Longleftrightarrow\quad \mathcal{G}\text{ is realizable}.

The surrounding discussion places this claim in the context of Hilbert's Tenth problem: realizability for \otimes graphs with cardinal constraints of the form pq|p|\leq |q| is stated to be undecidable because it is reducible to HTP. The proposed equivalence would give a direct realization of termination behavior by such graph instances; no resolution is supplied in the source.

Sources & referencesView supporting material

Primary source

Domenico Cantone and Pietro Ursino, “Hilbert's Tenth problem and NP-completeness of Boolean Syllogistic with unordered cartesian product”, arXiv:2101.00198 (2021).

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.