Theory of Computational Complexity, 2nd Edition

Chapter 7

Polynomial-Time Isomorphism

Two decision problems are said to be polynomial-time isomorphic if there is a membership-preserving one-to-one correspondence between the instances of the two problems, which is both polynomial-time computable and polynomial-time invertible. Thus, this is a stronger notion than the notion of equivalence under the polynomial-time many-one reductions. It has, however, been observed that many reductions constructed between natural NP-complete problems are not only many-one reductions but can also be easily converted to polynomial-time isomorphisms. This observation leads to the question of whether two NP-complete problems must be polynomial-time isomorphic. Indeed, if this is the case then, within a polynomial factor, all NP-complete problems are actually identical and any heuristics for a single NP-complete problem works for all of them. In this chapter, we study this question and the related questions about the isomorphism of EXP-complete and P-complete problems.

7.1 Polynomial-Time Isomorphism

Let us start with a simple example.

Example 7.1

Recall the decision problems IS and CLIQUE from Chapter 2:

INDEPENDENT SET (IS): Given a graph G and an integer k > 0, determine whether G has an independent set of size atleast k.CLIQUE: Given a graph G and an integer k > 0, determine whether G has a clique of size at least k.

For any graph , let ...