The bounded-width boundary conjecture for Borel homomorphism problems
The bounded-width boundary conjecture for Borel homomorphism problems
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 and ; a problem is bounded width when it is solvable by a bounded-width constraint-propagation procedure.
Bounded-width boundary conjecture. A homomorphism problem is iff it is not -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
Sign in to submit a solution.
No solutions have been posted yet.