Many-One Reducibility of decision problems for complexity theory?

Question

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?

Answer 1

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.