I was given a question

Given the following constraint networks $X$, $Y$ and $Z$ with four variables $x_1, x_2, x_3$ and $x_4$ all defined on the same domain values $\{\text{red}, \text{blue} \}$. The constraints in the network are as follows:

  • X: R13 = R14 = R23 = R24 = {(red, blue) (blue, red)}
  • Y: R13 = R14 = R23 = R24 = {(red, blue) (blue, red)}, R12={(red, red) (blue, blue)}
  • Z: R13 = R14 = R23 = R24 = {(red, blue) (blue, red)} , R34={(red, blue) (blue, red)}
  1. Identify which of them are equivalent:

  2. In the above question, the equivalent-networks are equivalent because some operation between some of the relations of these networks makes them the same. What is the name of the operation?

    • Composition
    • Union
    • Intersection
    • Set-difference

Now, I know that $X$ and $Y$ are equivalent because $Y$ is a tighter form of $X$. But I don't know the answer to the second question. Which of the options above are correct?

I think the answer is intersection, but not sure as to how to prove it.

  • $\begingroup$ Maybe you should describe what $R12$, etc., are here, and how are they related to the variable $x_1$. Moreover, for people not familiar with the topic (like me), I would suggest that you provide a reference (that you're using) that describes the "constraint network", so that we are on the same page, and it could be helpful to those attempting to answer this question (even though this seems to be a standard approach to solve CSPs, e.g. ics.uci.edu/~csp/r17-survey.pdf). $\endgroup$
    – nbro
    Feb 6 at 16:21

Your Answer

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

Browse other questions tagged or ask your own question.