(on polynomial-time invertible reductions (following [37])): We say
that a set S is markable if there exists a polynomial-time (marking) algorithm M such
that
1. For every x, α ∈ {0, 1}∗ it holds that
(a) M(x, α) ∈ S if and only if x ∈ S.
(b) |M(x, α)| > |x|.
2. There exists a polynomial-time (de-marking) algorithm D such that, for every
x, α ∈ {0, 1}∗, it holds that D(M(x, α)) = α.
Note that all natural NP-sets (e.g., those considered in this chapter) are markable (e.g.,
for SAT, one may mark a formula by augmenting it with additional satisfiable clauses
that use specially designated auxiliary variables). Prove that if S is Karp-reducible to
S and S is markable then S is Karp-reducible to S by a length-increasing, one-toone, and polynomial-time invertible mapping.
34 Infer that for any natural NP-complete
problem S, any set in N P is Karp-reducible to S by a length-increasing, one-to-one,
and polynomial-time invertible mapping.
Guideline: Let f be a Karp-reduction of S to S, and let M be the guaranteed marking
algorithm. Consider the reduction that maps x to M( f (x), x).