Reduction (complexity)

This product was added to computer science because of the content, defects on the quality assurance side of the editor. This is done to bring the quality of the articles from the computer science subject area to an acceptable level. Help us to eliminate the substantive shortcomings of this article and take part you in the discussion! ( )

The reduction is a method of theoretical computer science, in which a problem is attributed to another. Is there an algorithm for the second problem, it can also be the first to solve via reduction. The reducibility is therefore a relation on the set of problems, by which the predictability or complexity of two problems can be related to each other.

The basic idea of ​​reductions for the investigation of problems to use goes back to an essay by the mathematician Emil Post in 1944.

We distinguish between different types of reductions. The most common are the One -one or many-one reduction, and the Truth -table and Turing reduction (the latter named after Alan Turing ). Each of them contains each of the preceding as a special case.

While in computability theory usually sufficient to establish the existence of a certain reduction between two problems, additional requirements are imposed on the resource consumption of the reduction in complexity theory. Common resources are this time or space. This leads to the concepts of Karp (after Richard M. Karp ) and Cook reduction ( by Stephen Cook).

Accruals

Conventions

Reductions are usually considered only for decision problems, in which, therefore, asked whether a given object has a particular property or not. More specifically, it is even sufficient - by a suitable Gödelization - only decision problems of sets of natural numbers to look at. Thus the aim is always the characteristic function of a subset of calculating. This approach has the advantage that now the problems can be identified with the subsets themselves. However, it is quite possible, the following definitions to be transferred to optimization and search problems.

Reductions in computability theory

Be sets of natural numbers.

• Hot many-one - reducible to - spelling - if there is a total ( Turing ) are computable function, for

• Hot one-one - reducible to - spelling - if it can be chosen injective.

• Hot truth -table- reducible to - spelling - if there is a Turing machine that this is true for every natural number a propositional formula (or its Gödel number ) is calculated and natural numbers, like this:

• Hot Turing reducible to - spelling - if there is an oracle Turing machine with oracle that computes the characteristic function of.

Reduction in complexity theory

In principle, the same reductions as in computability theory are considered in complexity theory, but their calculation may now need only one ( in the size of the input ) limited amount of memory or CPU time.

Especially often involve the following types are considered:

Be one of the above reductions, is also a natural number, the length of the input in bits.

• The reduction in hot polynomial time limited or Polynomialzeitreduktion - spelling - if there is a constant and a ( oracle ) Turing machine, calculated and thereby performs only a maximum of many bit operations for every input the.

• The reduction in hot logarithmic space is limited - spelling - if a corresponding Turing machine only describes a maximum memory cells. Those cells in which the original input is, are not taken into account, but then must also not be described, but only read.

It should be noted that any oracle requests require only a single arithmetic step and the replies received each occupy only a single memory cell. For the O- notation used see also: Landau symbols

The polynomial- time many-one reductions () are also called Karp - reductions and polynomial time bounded Turing reductions ( ) are called Cook reductions.

Relationships of the various reductions

For sets of natural numbers is valid:

Each of these implications is strict.

The individual reductions mainly differ in how often a ( hypothetical ) algorithm may be used for to help you decide. In the many-one reduction is only for a single number - namely straight - to examine the origin, the result must then be issued without further processing. Truth -table reductions allow finally by many requests and the subsequent processing of the information obtained. The formula is usually given as a truth table, where the name of the reduction comes from. However, any requests to proceed in parallel at a single time during the calculation. In the Turing reduction eventually as many requests may be made at any time of calculation, it is also possible to proceed depending on the responses received to branch.

With increasing generality but decreases the selectivity of the reduction, it can no longer distinguish between a set and its complement, for example, under Turing reduction. For this reason is not known, for example, whether the complexity class NP is closed under Cook reduction.

Properties and examples

• Between two sets, a reduction and is the second or decidable enumerable recursively, this feature automatically comes to the first set.

• All reductions form Präordnungen on the power set, in particular they are all transitive.

• The amounts of the even and odd natural numbers can be mutually successive one-one - cut, they are one-one - equivalent:

• A set is recursively enumerable if and only if it can be reduced to the halting problem many-one.

• The special halting problem, the retention problem and the general halting problem, in turn, are interconnected one-one equivalent.

• The complement of the special halting problem can be attributed to this Turing reduction. But apparently there are no many-one reduction, because the complement is not enumerable.

• Every problem from NP can be polynomially time- limited many-one on the satisfiability of propositional logic reduce. Since the latter is itself in NP, it is called NP -complete.