2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Haha, nice — I had a feeling the question was equivalent to solving P = NP. I hope they don’t re-ask that question this year… :) $\endgroup$ – Lynn Jan 9 '17 at 1:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.