0

Why do we call Turing reductions many-one reductions? I looked the origin of many-one notation on Google but found nothing.

oobarbazanoo
  • 141
  • 7
  • 2
    A Turing reduction is something different from a many-one reduction. (Or rather, every many-one reduction is also a Turing reduction, but not all Turing reductions are many-one reductions). – hmakholm left over Monica Feb 03 '17 at 22:28
  • The comment by @HenningMakholm is correct. Let me add that many-one reductions were so named to distinguish them from the even more restrictive class of one-one reductions (which are, not surprisingly, defined just like many-one reductions with the added requirement that the reducing function be one-to-one). – Andreas Blass Feb 03 '17 at 22:37

0 Answers0