Бірге-бірге азайтудың түрлері

Type of Turing reduction
In computability theory and computational complexity theory, a many one reduction (also called mapping reduction) is a reduction that converts instances of one decision problem (whether an instance is in ) to another decision problem (whether an instance is in ) using a computable function. The reduced instance is in the language if and only if the initial instance is in its language Thus if we can decide whether instances are in the language , we can decide whether instances are in its language by applying the reduction and solving for Thus, reductions can be used to measure the relative computational difficulty of two problems. It is said that reduces to if, in layman's terms is at least as hard to solve as This means that any algorithm that solves can also be used as part of a (otherwise relatively simple) program that solves
Many one reductions are a special case and stronger form of Turing reductions. Later Norman Shapiro used the same concept in 1956 under the name strong reducibility.

A set is called many one complete, or simply m complete, iff is recursively enumerable and every recursively enumerable set is m reducible to .

The relation indeed is an equivalence, its equivalence classes are called m degrees and form a poset with the order induced by .

A polynomial time many one reduction from a problem A to a problem B (both of which are usually required to be decision problems) is a polynomial time algorithm for transforming inputs to problem A into inputs to problem B, such that the transformed problem has the same output as the original problem. An instance x of problem A can be solved by applying this transformation to produce an instance y of problem B, giving y as the input to an algorithm for problem B, and returning its output. Polynomial time many one reductions may also be known as polynomial transformations or Karp reductions, named after Richard Karp. A reduction of this type is denoted by or .