Equivalent CSPs

From Glossary

Jump to: navigation, search


Consider two constraint satisfaction problems LaTeX: P_1 and LaTeX: P_2 and a sequence LaTeX: X of their common variables. We say that LaTeX: P_1 and LaTeX: P_2 are equivalent w.r.t LaTeX: X if

  • for every solution LaTeX: d to LaTeX: P_1 a solution to LaTeX: P_2 exists that coincides with LaTeX: d on the variables in X, and
  • for every solution LaTeX: e to LaTeX: P_2 a solution to LaTeX: P_1 exists that coincides with LaTeX: e on the variables in X.


Views
Personal tools