1
$\begingroup$

A many-one reduction of problem $A$ to problem $B$ is essentially a function that converts a problem instance in problem $A$ to an instance in $B$. This allows you to use a $B-$solver one time to solve this converted instance, in order to solve an $A$-instance.

To show that $A$ is in NP-complete, people use reducibillity arguments to reduce (in polynomial time) an arbitrary problem in NP to $A$, but as far as I know this is not necessarily a many-one reduction.

My question is: How many of these reductions in the context of NP-completeness are many-one reductions? How significantly would the complexity class change if we would require many-one reductions?

Improve this question
$\endgroup$
3
  • $\begingroup$ "in the complexity class NP-complete people use reducibillity arguments to reduce A to B but this is not necessarily a many-one reduction." -- citation needed. If they do that, they are probably wrong. $\endgroup$
    – Raphael ♦
    Oct 29 '18 at 13:38
  • $\begingroup$ @Raphael, I was sloppy. is this better? $\endgroup$
    – user600670
    Oct 29 '18 at 14:31
  • $\begingroup$ My question stands. $\endgroup$
    – Raphael ♦
    Oct 29 '18 at 22:24
2
$\begingroup$

NP-hardness (and so NP-completeness) are defined using many-one reductions. When you show that a problem is NP-hard, you have to follow the definition and use many-one reductions. All proofs that you see of NP-hardness use many-one reductions.

One thing to note is that usually, one does not show how to reduce an arbitrary problem in NP to the target problem. Rather, one reduces a problem already known to be NP-hard to the target problem. The starting point of this endeavor is Cook's theorem (independently proved by Levin), which shows that SAT is NP-hard.

The other common type of reduction is oracle reduction (there are other types as well, but they are less common). Oracle reductions cannot distinguish NP from coNP: every coNP-hard problem in the many-one sense is NP-hard for oracle reductions. Most researchers believe that NP is different from coNP, and this is one of the reasons we insist on using many-one reductions.

Improve this answer
$\endgroup$
1
  • $\begingroup$ "All proofs that you see of NP-hardness use many-one reductions." -- Alas, there are frequent exceptions to that. Those people are wrong, of course, but an unwary reader may easily get confused. $\endgroup$
    – Raphael ♦
    Oct 29 '18 at 22:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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