# Many-One Reducibility of decision problems for complexity theory?

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?

• "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.
– Raphael
Oct 29, 2018 at 13:38
• @Raphael, I was sloppy. is this better? Oct 29, 2018 at 14:31
• My question stands.
– Raphael
Oct 29, 2018 at 22:24

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.

• "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.
– Raphael
Oct 29, 2018 at 22:23