ABSTRACT
The “natural” NP complete decision problems are very much alike. They not only are of the same complexity, but also are in the same polynomial-time isomorphism degree, and the reductions/isomorphisms between many of these problems are parsimonious. This chapter describes the existence of reductions that preserve the properties of the witness spaces. Instead of just asking that the reduction preserves the number of solutions, one require an isomorphism between the witnesses. The chapter shows that even this extremely demanding reducibility notion can indeed often link the relations that define NP-complete problems. Yet, surprisingly, there exist very natural witness schemes for problems in the isomorphism degree of Sat for which it is unlikely that such a tight connection between these problems and Sat exists.
