Classification conjecture for the Exists Right-Factor Problem and bounded f-cores
Classification conjecture for the Exists Right-Factor Problem and bounded f-cores
Let a variety be a class of algebras defined by identities, let be a fixed algebra, and consider the Exists Right-Factor Problem for homomorphism factorization with fixed algebra . A variety has bounded -cores if there is a bound on the size of the -cores arising for its finite algebras.
Classification conjecture. The Exists Right-Factor Problem with fixed algebra is in polynomial time for a given variety if and only if the variety has bounded -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 -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.