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.
References
Primary source
Jan Grebík and Zoltán Vidnyánszky, “Complexity of Linear Equations and Infinite Gadgets”, arXiv:2501.06114 (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
No solutions have been posted yet.