ABSTRACT
The technique of transforming a problem into another in such a way that the solution of the latter entails, somehow, the solution of the former, is a classical mathematical technique that has found wide application in computer science since the seminal works of Cook [1] and Karp [2] who introduced particular kinds of transformations (called reductions) with the aim of studying the computational complexity of combinatorial decision problems. The interesting aspect of a reduction between two problems consists in its twofold application: on one side it allows to transfer positive results (resolution techniques) from one problem to the other and, on the other side, it may also be used for deriving negative (hardness) results. In fact, as a consequence of such seminal work, by making use of a specific kind of reduction, the polynomial-time Karp-reducibility, it has been possible to establish a complexity partial order among decision problems, which, for example, allows us to state that, modulo polynomial-time transformations, the stisfiability problem is as hard as thousands of other combinatorial decision problems, even though the precise complexity level of all these problems is still unknown.
