b c d e f g h --------------- 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0 (solutions that exist by definition) 1 0 1 0 1 0 1 0 --------------- .... 1 0 0 1 1 1 0 0 (other solutions are possible) .... This table is made of two parts. The first part contains the solutions that exist by definition of this problem; the second part (that may be empty) contains all other solutions. Since the columns of the table are by definition associated to the possible -tuples of values of the domain, every solution can be viewed as a function from a -tuple of elements to a single element. The function corresponding to a solution can be calculated from the first part of the table above and the solution. As an example, for the last solution marked in the table, this function can be determined for arguments as follows: first, these three values are the first part of the row "c" in the table; the value of the function is the value of the solution in the same column, that is, 0. A necessary condition for tractability is the existence of a solution for a universal gadget of some order that is part of some classes of functions. This result however only holds for reduced languages, which are defined below. Squashing functions and reduced domains Squashing functions are functions used to reduce the size of domain of constraint languages. A squashing function is defined in terms of a partition of the domain and a representative element for each set in the partition. The squashing function maps all elements of a set in the partition to the representative element of that set. For such a function being a squashing function it is also necessary that applying the function to all elements of a tuple of a relation in the language produces another tuple in the relation. The partition is assumed to contain at least a set of size greater than one. Formally, given a partition of the domain containing at least a set of size greater than one, a squashing function is a function such that for every in the same partition, and for every tuple , it holds . For constraint problems on a constraint language has a squashing function, the domain can be reduced via the squashing function. Indeed,