The bounded-width boundary conjecture for Borel homomorphism problems

About 1 year old · traced to

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.

References

Primary source

Jan Grebík and Zoltán Vidnyánszky, “Complexity of Linear Equations and Infinite Gadgets”, arXiv:2501.06114 (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.