Reduction (theoretical computer science)

The reduction is a method of theoretical computer science , in which a problem is attributed to another. If there is an algorithm for the second problem, the first can also be solved via the reduction. The reducibility is thus a relation to the amount of the problems, by which the predictability or the complexity of two problems may be related to each other.

The basic idea of ​​using reductions to investigate problems goes back to an essay by the mathematician Emil Post from 1944.

There are different types of reductions. The most common are the one-one or many-one reduction , as well as the truth table and Turing reduction (the latter named after Alan Turing ). Each of them contains the previous ones as a special case.

While in the calculability theory it is usually sufficient to prove the existence of a certain reduction between two problems, in the complexity theory additional requirements are placed on the resource consumption of the reduction. Common resources here are time or storage space. This leads to the terms Karp (after Richard M. Karp ) and Cook (after Stephen Cook ) reduction .

Delimitations

Conventions

Reductions are usually only considered for decision problems , in which the question is asked whether a certain object has a special property or not. More precisely, it is even sufficient - through a suitable godelization - to consider only decision problems of sets of natural numbers . The goal is always to calculate the characteristic function of a subset of . This approach has the advantage that the problems with the subsets themselves can now be identified. However, it is very easy to apply the following definitions to optimization and search problems . ${\displaystyle \chi }$ ${\displaystyle \mathbb {N} }$

Reductions in the computability theory

Let be sets of natural numbers. ${\displaystyle A,B\subseteq \mathbb {N} }$

• ${\displaystyle A}$is called many-one-reducible to - notation - if there is a total (Turing) calculable function for which ${\displaystyle B}$ ${\displaystyle A\preceq _{m}B}$ ${\displaystyle f\colon \mathbb {N} \to \mathbb {N} }$

${\displaystyle n\in A\Leftrightarrow f(n)\in B}$

applies.

• ${\displaystyle A}$hot one-one reducible to - writing if - it injective can be selected. ${\displaystyle B}$ ${\displaystyle A\preceq _{1}B}$ ${\displaystyle f}$

• ${\displaystyle A}$be called truth-table-reducible to - notation - if there is a Turing machine that calculates a propositional formula (or its Gödel number ) and natural numbers for every natural number , so that: ${\displaystyle B}$ ${\displaystyle A\preceq _{tt}B}$ ${\displaystyle n}$ ${\displaystyle \varphi (x_{1};\cdots ;x_{k})}$ ${\displaystyle b_{1};\cdots ;b_{k}\in \mathbb {N} }$

${\displaystyle n\in A\Leftrightarrow \varphi (\chi _{B}(b_{1});\cdots ;\chi _{B}(b_{k}))=1}$

The arity can depend on the entry . ${\displaystyle k}$ ${\displaystyle n}$

• ${\displaystyle A}$is called Turing-reducible to - notation - if there is an oracle-Turing machine with oracle for that calculates the characteristic function of . ${\displaystyle B}$ ${\displaystyle A\preceq _{T}B}$ ${\displaystyle B}$ ${\displaystyle \chi _{A}}$ ${\displaystyle A}$

• ${\displaystyle A}$is called enumerable reducible to - notation - if there is an enumeration operator for which applies. ${\displaystyle B}$ ${\displaystyle A\preceq _{e}B}$ ${\displaystyle \Psi }$ ${\displaystyle \Psi (B)=A}$

Reduction in complexity theory

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

The following types are particularly frequently considered:

Let one of the above reductions be, for a natural number also let the length of the input in bits . ${\displaystyle \preceq }$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle l(n)=\lfloor \log _{2}n\rfloor +1}$ ${\displaystyle n}$

• The reduction is called polynomial time-limited or polynomial time reduction - notation - if there is a constant and an (oracle) Turing machine that calculates and only performs a maximum of many bit operations for each input . ${\displaystyle \preceq ^{p}}$ ${\displaystyle c\in \mathbb {N} }$ ${\displaystyle \preceq }$ ${\displaystyle n}$ ${\displaystyle {\mathcal {O}}(l^{c}(n))}$

• The reduction is called logarithmically space-restricted - notation - if a corresponding Turing machine only writes at most memory cells. The cells in which the original entry is located are not taken into account, but may not be written to, only read. ${\displaystyle \preceq ^{log}}$ ${\displaystyle {\mathcal {O}}(\log l(n))}$

It should be noted that any oracle inquiries only need a single calculation step or the answers received only occupy a single memory cell. For the O notation used, see also: Landau symbols

The polynomial time constrained many-one reductions ( ) are also called Karp reductions and the polynomial time constrained Turing reductions ( ) are called Cook reductions . ${\displaystyle \preceq _{m}^{p}}$ ${\displaystyle \preceq _{T}^{p}}$

Relationships of the various reductions

The following applies to sets of natural numbers: ${\displaystyle A;B\subseteq \mathbb {N} }$

${\displaystyle A\preceq _{1}B\Rightarrow A\preceq _{m}B\Rightarrow A\preceq _{tt}B\Rightarrow A\preceq _{T}B}$ such as ${\displaystyle A\preceq _{tt}B\Rightarrow A\preceq _{e}B}$

Each of these implications are strict. In general, the enumerable reduction and the Turing reduction are incomparable. ${\displaystyle \preceq _{e}}$ ${\displaystyle \preceq _{T}}$

The individual reductions essentially differ in how often a (hypothetical) algorithm may be used to make a decision. With the many-one reduction, the affiliation to only one number - namely even - is checked; the result must then be output without further processing. Truth table reductions allow a finite number of queries and the subsequent processing of the information obtained . The formula is usually given as a truth value table , which is where the name of the reduction comes from. However, all queries must be made in parallel at a single point in time during the calculation. With the Turing reduction, any number of inquiries can be made at any point in the calculation, and it is also possible to branch the further procedure depending on the answers received. In the case of the enumerable reduction, on the other hand, no algorithm at all is required for the decision of more, but only an enumeration of the set (which cannot be calculated) . ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle f(n)}$ ${\displaystyle B}$ ${\displaystyle b_{i}}$ ${\displaystyle \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle \chi _{B}(b_{i})}$ ${\displaystyle B}$

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

Properties and examples

• If one of the above reductions exists between two sets, which is really weaker than the Turing reduction, and if the second set is decidable or recursively enumerable , then this property is automatically assigned to the first set.

• All reductions form pre-orders on the power set , in particular they are all transitive . ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$
• The recursively enumerable sets form exactly the minimal elements of the enumerable reduction . ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ ${\displaystyle \preceq _{e}}$
• With the Turing reduction , these are exactly the decidable quantities. ${\displaystyle \preceq _{T}}$
• The sets of even and odd natural numbers can be mutually reduced one-one-one, they are one-one-equivalent :

${\displaystyle \{2n\ |\ n\in \mathbb {N} \}\equiv _{1}\{2n+1\ |\ n\in \mathbb {N} \}}$

Both reductions are conveyed through the illustration . ${\displaystyle m\mapsto m+1}$

• A set can be recursively enumerated if and only if it can be reduced many-one to the holding problem . ${\displaystyle H}$

• The special halting problem , the -Halteproblem and the general halting problem in turn are equivalent to each other one-one. ${\displaystyle K}$ ${\displaystyle \varepsilon }$ ${\displaystyle H_{0}}$ ${\displaystyle H}$

• The complement of the special holding problem can be reduced to this Turing . But apparently there is no many-one reduction , because the complement cannot be enumerated. ${\displaystyle {\overline {K}}\preceq _{T}K}$ ${\displaystyle {\overline {K}}\npreceq _{m}K}$

• Designate a simple graph (its Gödel number), its complement and a natural number, then it is explained by a polynomial time-limited one-one reduction from the vertex coverage problem to the clique problem . ${\displaystyle (V,E)}$ ${\displaystyle (V,{\overline {E}})}$ ${\displaystyle k}$ ${\displaystyle ((V,E),\ k)\mapsto ((V,{\overline {E}}),\ |V|-k)}$

• Every problem from NP can be reduced polynomially time-limited many-one to the satisfiability problem of propositional logic . Since the latter itself is also in NP, it is called NP-complete . ${\displaystyle SAT}$

Grade

Let one of the above reductions be as is for all preorders ${\displaystyle \preceq }$

${\displaystyle A\equiv B\Leftrightarrow A\preceq B\land A\succeq B}$

explains an equivalence relation . The equivalence classes are called degrees . Due to the lack of antisymmetry , they usually contain more than one set, usually a countable infinite number. The degrees partition and are partially ordered by . The best known is the structure of the Turing degrees , also called simply degrees , i.e. the degrees relating to the Turing reduction. ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ ${\displaystyle \preceq }$ ${\displaystyle T}$

literature

• Katrin Erk, Lutz Priese: Theoretical Computer Science. A comprehensive introduction ; 2nd expanded edition; Springer-Verlag, Berlin et al. 2002, ISBN 3-540-42624-8 ( Springer textbook )
• John E. Hopcroft , Rajeev Motwani , Jeffrey Ullman : Introduction to Automata Theory, Formal Languages, and Complexity Theory . 2., revised. Edition. Pearson Studium, Munich 2002, ISBN 3-8273-7020-5 (Original title: Introduction to automata theory, languages, and computation . Translated by Sigrid Richter, Ingrid Tokar).
• Hartley Rogers, Jr .: Theory of Recursive Functions and Effective Computability ; McGraw-Hill, New York NY et al. 1967 ( McGraw-Hill Series in Higher Mathematics ), (Reprint: MIT Press , Cambridge MA et al. 1987, ISBN 0-262-68052-1 )
• Ingo Wegener : Theoretical Computer Science: An Algorithmic Introduction ; 3rd revised edition; Teubner-Verlag, Wiesbaden 2005, ISBN 3-8351-0033-5 ( guidelines for computer science )

Individual evidence

1. ↑ E. Post: Recursively enumerable sets of positive integers and Their decision problems. Bulletin of the American Mathematical Society, Volume 50 (1944), No. 5, pp. 284-316 (online, PDF file; 4.0 MB) .