2
$\begingroup$

I have read the question asked here Is polynomial reduction reversible and the logic actually makes sense to me. In other words, if A is polynomially reducible to B, it means that A <= B in terms of hardness.

However, when I thought more about the reduction process, I am confused. As far as I can understand, the NP-Complete reduction process is as follows:

(1) Find some NP-Complete problem (i.e. A), convert its inputs and output to the inputs and output of the problem we want to prove (i.e. B)

(2) Show that if A is YES, then B is YES

(3) Show that if B is YES, then A is YES.

Then I also read several classic reduction proofs, and here is my confusing part. In all the reductions I read, step (1) seems to be a "one-to-one mapping" between the inputs of A to the inputs B. For example, minimum set cover (MSC) to minimum vertex cover (MVC), edges in MVC is elements in MSC and nodes in MVC is sets in MSC. Since it's a "one-to-one mapping" of inputs A to inputs B, if we can convert the inputs of A to the inputs of B, then we can always convert the inputs of B to the inputs of A. In this case, isn't step (1) a reversible process? I am not sure if "one-to-one mapping" is the correct terminology, but the main idea I want to say is "the specific way" of mapping inputs of A to the inputs of B. Is there any reduction example that maps the input from A to the inputs of B, but the mapping is not reversible, i.e. can't map the inputs of B back to A?

What's more, no matter if we convert A to B or convert B to A, I think step (2) and step (3) above are still the same. Therefore, I am really confused about which part makes the NP-Complete reduction not reversible?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Here is a concrete example. Let $A$ be the problem in which all instances are NO instances, and let $B$ be the problem with a unique YES instance $1$. The function $f(x) = 0$ is a reduction from $A$ to $B$, but there is no reduction from $B$ to $A$, since there is nothing we can map $1$ into.

The asymmetric part in the reduction is the reduction itself, which is not guaranteed to be invertible. As the example above shows, it doesn't have to be one-to-one either, though usually we can make it so.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks, could you explain a little more about your reduction above? I am really new to this, I didn't quite understand how A reduces to B. What are their input and outputs? How do we convert A's inputs to B? $\endgroup$
    – Francis
    Commented Feb 3, 2022 at 15:22
  • $\begingroup$ The reduction takes an arbitrary instance of A to the instance 0 of B; instead of 0 you can take any NO instance of B. $\endgroup$
    – Yuval Filmus
    Commented Feb 3, 2022 at 15:37
  • $\begingroup$ Decision problems get an instance as input (in this case, you can use binary strings for the inputs, but it doesn’t really matter), and output either YES or NO. $\endgroup$
    – Yuval Filmus
    Commented Feb 3, 2022 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.