over a set of variables, and the need to store all tuples of values that satisfy a given group of constraints. Necessary condition for tractability A necessary condition for the tractability of a constraint language based on the universal gadget has been proved. The universal gadget is a particular constraint satisfaction problem that was initially defined for the sake of expressing new relations by projection. The universal gadget A relation that is not present in a constraint language may be "simulated" by constraints using the relations in the language. In particular, a new relation can be created by placing a set of constraints and using only some of their variables. If all other constraints use only these variables, this set of constraints forces these variable to only assume specific values, practically simulating a new relation. Every constraint satisfaction problem and subset of its variables defines a relation, which is composed by all tuples of values of the variables that can be extended to the other variables to form a solution. Technically, this relation is obtained by projecting the relation having the solutions as rows over the considered variables. The universal gadget is based on the observation that every relation that contains -tuples can be defined by projecting a relation that contains all possible columns of elements from the domain. As an example, the following tables shows such a projection: a b c d e f g h b d --------------- --- 1 1 1 1 0 0 0 0 -> 1 1 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 0 0 0 If the table on the left is the set of solutions of a constraint satisfaction problem, its variables and are constrained to the values of the table to the right. As a result, the constraint satisfaction problem can be used to set a constraint whose relation is the table on the right, which may not be in the constraint language. As a result, if a constraint satisfaction problem has the table on the left as its set of solutions, every relation can be expressed by projecting over a suitable set of variables. A way for trying to obtain this table as the set of solution is to place every possible constraint that is not violated by the required solutions. As an example, if the language contains the binary