Answers.Body: <p>If we can do some reduction in the search space using CSP (constraint propagation) we can drastically reduce the search space or sometimes completely avoid the need for a search by directly reaching the solutions (for e.g. with variables having their domains reduced to size one). It could also happen that we come to a point when a variable domain size becomes zero, in that case no solution exists, given the constraints, so no need for a search. </p>
  
  <p>Constraint propagation basically involves the concept of enforcing <strong>local consistency</strong> (this is done by enforcing node-consistency, arc-consistency, path-consistency and also global constraints using Alldiif or Atmost). </p>
  
  <p>The terms: <strong>nodes</strong>, <strong>arc</strong>, <strong>path</strong>, etc. basically reflects a CSP problem represented as a graph with nodes as the variables and the arcs/edges as constraints. The process is simply to remove values from the domains of the variables that are inconsistent. Algorithms such as <strong>AC-3</strong>, <strong>PC-2</strong>, etc. precisely are for these purposes.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-20T14:07:40.763Z
Answers.LastActivityDate: 2019-12-20T14:07:40.763Z
Answers.UserDisplayName: MuneshSingh
Body: <p>In the Constraint Propagation in CSP, it is often stated that <em>pre-processing</em> can solve the whole problem, so no search is required at all. And the key  idea is <strong>local consistency</strong>. What does this actually mean?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-02T13:03:22.060Z
Comments.Text: Have a look at [https://en.wikipedia.org/wiki/Local_consistency](https://en.wikipedia.org/wiki/Local_consistency).
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-09-06T05:28:04.940Z
Comments.Text: I think the consistency propagation method only works for 2-SAT problems, no?
Comments.UserDisplayName: PeaBrane
Tags: <terminology><definitions><constraint-satisfaction-problems>
Title: What is local consistency in constraint satisfaction problems?
UserDisplayName: Lexi
ThreadText: # What is local consistency in constraint satisfaction problems?
  
  (Asked by: username_0 on 2019-05-02)
  
  In the Constraint Propagation in CSP, it is often stated that *pre-processing* can solve the whole problem, so no search is required at all. And the key idea is **local consistency**. What does this actually mean?
  
  **Tags:** terminology, definitions, constraint-satisfaction-problems
  > **Comments:**
  > **username_1**: Have a look at [https://en.wikipedia.org/wiki/Local_consistency](https://en.wikipedia.org/wiki/Local_consistency).  
  > **username_2**: I think the consistency propagation method only works for 2-SAT problems, no?  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2019-12-20. Score: 0
  
  If we can do some reduction in the search space using CSP (constraint propagation) we can drastically reduce the search space or sometimes completely avoid the need for a search by directly reaching the solutions (for e.g. with variables having their domains reduced to size one). It could also happen that we come to a point when a variable domain size becomes zero, in that case no solution exists, given the constraints, so no need for a search.
  
  Constraint propagation basically involves the concept of enforcing **local consistency** (this is done by enforcing node-consistency, arc-consistency, path-consistency and also global constraints using Alldiif or Atmost).
  
  The terms: **nodes**, **arc**, **path**, etc. basically reflects a CSP problem represented as a graph with nodes as the variables and the arcs/edges as constraints. The process is simply to remove values from the domains of the variables that are inconsistent. Algorithms such as **AC-3**, **PC-2**, etc. precisely are for these purposes.
  
  
  ---
  
  