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