Hidden transformation

Hidden transformation

The hidden transformation reformulates a constraint satisfaction problem in such a way all constraints have at most two variables. The new problem is satisfiable if and only if the original problem was, and solutions can be converted easily from one problem to the other.

There are a number of algorithms for constraint satisfaction that work only on constraints that have at most two variables. If a problem has constraints with a larger arity (number of variables), conversion into a problem made of binary constraints allows for execution of these solving algorithms. Constraints with one, two, or more variables are called unary, binary, or "higher-order" constraints. The number of variables in a constraint is called its "arity".

The hidden transformation converts an arbitrary constraint satisfaction problem into a binary one. The transformation is similar to that generating the dual problem. The problem is added new variables, one for each constraint of the original problem. The domain of each such variable is the set of satisfying tuples of the corresponding constraint. The constraints of the new problem enforce the value of the original variables to be consistent with the values of the new variables. For example, if the new variables c, corresponding to the old constraint C(x,y) can assume values (1,2) and (2,0), two new constraints are added: the first one enforces x to take value 1 if c=(1,2) value 2 if c=(2,0), and vice versa. The second condition enforces a similar condition for variable y.

The graph representing the result of this transformation is bipartite, as all constraints are between a new and an old variable. Moreover, the constraints are functional: for any given value of a new variable, only one value of the old variable may satisfy the constraint.

References

*cite journal
first=Fahiem
last=Bacchus
coauthors=Xinguang Chen, Peter van Beek, Toby Walsh
title=Binary vs. Non-Binary Constraints
journal=Artificial Intelligence
volume=140
issue=1/2
pages=1–37
year=2002
url=http://www.cs.toronto.edu/~fbacchus/Papers/bcvwaij02.pdf
doi=10.1016/S0004-3702(02)00210-2


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Hidden variables — may refer to:* In physics, Hidden variable theories are a class of theories trying to explain away the statistical nature of quantum mechanics. * In statistics, Latent variables are variables that are inferred from other observed variables. * In… …   Wikipedia

  • Transformation problem — In 20th century discussions of Karl Marx s economics the transformation problem is the problem of finding a general rule to transform the values of commodities (based on labour according to his labour theory of value) into the competitive prices… …   Wikipedia

  • Inversion transformation — Inversion transformations are a natural extension of Poincaré transformations to include all conformal one to one transformations on coordinate space time. They are less studied in physics because unlike the rotations and translations of Poincaré …   Wikipedia

  • Spiritual transformation — is the act of transforming the deepest aspects of the human spirit via a self induced or divine act.ee also*Integral transformative practice *Transpersonal psychology *Sivananda *MeditationThe Way of Spiritual Transformationby Hieromonk… …   Wikipedia

  • creative transformation + biology —    by John Protevi   Biology seeks to explain resemblance and novelty in living things across multiple spatial (molecular, organic, systemic, organismic, specific, and ecological) and temporal (developmental, physiological, reproductive, and… …   The Deleuze dictionary

  • creative transformation + biology —    by John Protevi   Biology seeks to explain resemblance and novelty in living things across multiple spatial (molecular, organic, systemic, organismic, specific, and ecological) and temporal (developmental, physiological, reproductive, and… …   The Deleuze dictionary

  • Constraint satisfaction dual problem — The dual problem is a reformulation of a constraint satisfaction problem expressing each constraint of the original problem as a variable. Dual problems only contain binary constraints, and are therefore solvable by algorithms tailored for such… …   Wikipedia

  • Metamaterial cloaking — Electromagnetism Electricity · …   Wikipedia

  • List of Dragon Ball Z Kai episodes — Japanese promotional poster of Dragon Ball Kai Dragon Ball Z Kai (known in Japan as Dragon Ball Kai) is a revised version of the ani …   Wikipedia

  • KABBALAH — This entry is arranged according to the following outline: introduction general notes terms used for kabbalah the historical development of the kabbalah the early beginnings of mysticism and esotericism apocalyptic esotericism and merkabah… …   Encyclopedia of Judaism

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”