Feder–Vardi dichotomy conjecture for constraint satisfaction problems
Statement
A relational structure is a structure consisting of a domain together with relations of prescribed names and arities. For a fixed relational structure , is the decision problem whose instances are relational structures over the same vocabulary as , with question whether there is a homomorphism .
Feder–Vardi dichotomy conjecture. For any relational structure , is either NP-complete or polynomial-time solvable.
This is a major open problem in computational complexity. It is known for graph homomorphisms with one symmetric binary relation by the Hell–Nešetřil dichotomy theorem, and Feder and Vardi showed that a dichotomy for bipartite digraph homomorphism problems would imply the conjecture.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.