The bounded-width boundary conjecture for Borel homomorphism problems

From papers

A homomorphism problem is a decision problem asking whether a given structure admits a homomorphism to a fixed template. In the Borel setting, its descriptive complexity is measured using the projective classes Π11\mathbf{\Pi}^1_1 and Σ21\mathbf{\Sigma}^1_2; a problem is bounded width when it is solvable by a bounded-width constraint-propagation procedure.

Bounded-width boundary conjecture. A homomorphism problem is Π11\mathbf{\Pi}^1_1 iff it is not Σ21\mathbf{\Sigma}^1_2-complete iff it is bounded width.

This conjecture proposes that bounded width is exactly the boundary between the simpler and harder Borel homomorphism problems. The surrounding discussion presents it as a possible scenario suggested by Thornton's work; its general status is not established here.

Progress summary

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

Sources & referencesView supporting material

Primary source

Jan Grebík and Zoltán Vidnyánszky, “Complexity of Linear Equations and Infinite Gadgets”, arXiv:2501.06114 (2025).

Solutions 0

No solutions have been posted yet.