ABSTRACT
There is little doubt that the notion of reducibility is the most useful tool that complexity theory has delivered to the rest of the computer science community. Formost computational problems that arise in real-world applications, such as theTraveling Sales-
person Problem, we still know only a little about their deterministic time or space complexity. We cannot now tellwhether classes such asP andNPare distinct.Andyet, evenwithout suchhardknowledge, it has been useful in practice to take some new problem A whose complexity needs to be analyzed, andannounce thatAhas roughly the samecomplexity as theTravelingSalespersonProblem,by exhibiting efficientways of reducing each problem to the other. Thus, we can say a lot about problems being equivalent in complexity to each other, even if we cannot pinpoint what that complexity is. One reason for this success is thatwhen one partitions themany thousands of real-world computa-
tional problems into equivalence classes according to the reducibility relation, there are surprisingly few classes in this partition. Thus, the complexity of almost any problem arising in practice can be classified by showing that it is equivalent to one of the short list of representative problems. It was not originally expected that this would be the case.
