Are finite-domain binary constraint satisfaction problems solvable in polynomial time? Suppose a CSP has $n$ variables with finite domains of maximal size $d$. Furthermore, all constraints on the variables are binary. Can such a CSP be solved in polynomial time in $n$ and $d$?


This was an exam question on last year’s AI exam, but I’m not sure how to solve it.

I know the problem of graph coloring is easily reduced to such a binary CSP, so solving them is NP-complete. Thus, I’m pretty sure that there is no known polynomial-time algorithm. Can I prove that there isn’t one?
I don't know, but if you manage, make sure to let us know. 

The reduction seems easy indeed, with $d$ mapping to the number of colors and each constraint to an edge.

However, a polynomial-time algorithm for any $\mathcal{NP}$-complete problem exists if and only if $\mathcal{P} =\mathcal{NP}$; doing what you ask would imply $\mathcal{P} \neq \mathcal{NP}$.