Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Interchangeability algorithm
open-in-new
<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, an interchangeability algorithm is a technique used to more efficiently solve <a href="/facts/Constraint_satisfaction_problem/oKCeIV2L">constraint satisfaction problems</a> (CSP). A CSP is a mathematical problem in which objects, represented by variables, are subject to constraints on the values of those variables; the goal in a CSP is to assign values to the variables that are consistent with the constraints. If two variables <i>A</i> and <i>B</i> in a CSP may be swapped for each other (that is, <i>A</i> is replaced by <i>B</i> and <i>B</i> is replaced by <i>A</i>) without changing the nature of the problem or its solutions, then <i>A</i> and <i>B</i> are <i>interchangeable</i> variables. Interchangeable variables represent a symmetry of the CSP and by exploiting that symmetry, the <a href="/facts/Feasible_region/cJUKNCmM">search space</a> for solutions to a CSP problem may be reduced. For example, if solutions with <i>A</i>=1 and <i>B</i>=2 have been tried, then by interchange symmetry, solutions with <i>B</i>=1 and <i>A</i>=2 need not be investigated. </p><p>The concept of interchangeability and the interchangeability algorithm in constraint satisfaction problems was first introduced by Eugene Freuder in 1991. The interchangeability algorithm reduces the search space of <a href="/facts/Backtracking_search/Jm9vDUk8">backtracking search</a> algorithms, thereby improving the efficiency of <a href="/facts/NP-completeness/NFPv56DU">NP-complete</a> CSP problems. </p>