Classification conjecture for the Exists Right-Factor Problem and bounded f-cores

Let a variety be a class of algebras defined by identities, let ZZ be a fixed algebra, and consider the Exists Right-Factor Problem for homomorphism factorization with fixed algebra ZZ. A variety has bounded ff-cores if there is a bound on the size of the ff-cores arising for its finite algebras.

Classification conjecture. The Exists Right-Factor Problem with fixed algebra ZZ is in polynomial time for a given variety if and only if the variety has bounded ff-cores.

This conjecture proposes a complete classification of when the fixed-algebra Exists Right-Factor Problem is solvable in polynomial time. The preceding discussion notes relationships among three conditions concerning bounded ff-cores, but does not establish either implication in full; the conjecture is therefore presented as an open speculation.

Sources & referencesView supporting material

Primary source

Kevin M. Berg, “The Complexity of Homomorphism Factorization”, arXiv:1901.01817 (2019).

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.