# 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?

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}$.