|
In computability theory and computational complexity theory, a reduction is a transformation of one problem into another problem. Depending on the transformation used this can be used to define complexity classes on a set of problems. Computability theory is the branch of theoretical computer science that studies which problems are computationally solvable using different models of computation. ...
As a branch of the theory of computation in computer science, computational complexity theory describes the scalability of algorithms, and the inherent difficulty in providing scalable algorithms for specific computational problems. ...
In theoretical computer science, a computational problem is a mathematical object representing a question that computers might want to solve. ...
In computational complexity theory, a complexity class is a set of problems of related complexity. ...
Intuitively, if problem A is reducible to problem B, a solution to B gives a solution to A. Thus, solving A cannot be harder than solving B. We write A ≤ B, usually with a subscript on the ≤ to indicate the type of reduction being used.
Gentle Introduction Often we find ourselves trying to solve a problem that is similar to a problem we've already solved. In these cases, often a quick way of solving the new problem is to transform each instance of the new problem into instances of the old problem, solve these using our existing solution, and then use these to obtain our final solution. This is perhaps the most obvious use of reductions.
Another, more subtle use is this: suppose we have a problem that we've proven is hard to solve, and we have a similar new problem. We might suspect that it, too, is hard to solve. We argue by contradiction: suppose the new problem is easy to solve. Then, if we can show that every instance of the old problem can be solved easily by transforming it into instances of the new problem and solving those, we have a contradiction. This establishes that the new problem is also hard.
A very simple example of a reduction is from multiplication to squaring. Suppose all we know how to do is to add, subtract, take squares, and divide by two. We can use this knowledge, combined with the following formula, to obtain the product of any two numbers:
- a × b = ((a + b)2 - a2 - b2)/2.
We also have a reduction in the other direction; obviously, if we can multiply two numbers, we can square a number. This seems to imply that these two problems are equally hard. This kind of reduction corresponds to Turing reduction. In computability theory, a Turing reduction from a problem A to a problem B, named after Alan Turing, is a reduction which easily solves A, assuming B is easy to solve (Rogers 1967, Soare 1987). ...
However, the reduction becomes much harder if we add the restriction that we can only use the squaring function one time, and only at the end. In this case, even if we're allowed to use all the basic arithmetic operations, including multiplication, no reduction exists in general, because we may have to compute an irrational number like  from rational numbers. Going in the other direction, however, we can certainly square a number with just one multiplication, only at the end. Using this limited form of reduction, we have shown the unsurprising result that multiplication is harder in general than squaring. This corresponds to many-one reduction. In mathematics, an irrational number is any real number that is not a rational number, i. ...
In computational complexity theory, a many-one reduction is a reduction which converts instances of a decision problem problem A into instances of a decision problem B. We write A ≤m B or A is many-one reducible to B. If we have an algorithm N which solves instances...
Definition Given two subsets A and B of N and a set of functions F from N to N which is closed under composition, A is called reducible to B under F if A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, the terms, subset, superset and proper (or strict) subset or superset are used to describe the relation, called inclusion, of one set being contained inside another set. ...
In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ...
Partial plot of a function f. ...
In mathematics, a composite function, formed by the composition of one function on another, represents the application of the former to the result of the application of the latter to the argument of the composite. ...
 We write  Let S be a subset of P(N) and ≤ a reduction, then S is called closed under ≤ if A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, the terms, subset, superset and proper (or strict) subset or superset are used to describe the relation, called inclusion, of one set being contained inside another set. ...
 A subset A of N is called hard for S if  A subset A of N is called complete for S if A is hard for S and A is in S. In computational complexity theory, a computational problem is complete for a complexity class when it is, in a formal sense, one of the hardest or most expressive problems in the complexity class. ...
Examples - To show that a decision problem is undecidable a computable function can be used to transform it into another decision problem which is already known to be undecidable. In particular, we often show that a problem P is undecidable by showing that the halting problem reduces to P.
- The complexity classes P, NP and PSPACE are closed under polynomial-time reductions.
- The complexity classes L, NL, P, NP and PSPACE are closed under log-space reduction.
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. ...
Undecidable has more than one meaning: In mathematical logic: A decision problem is undecidable if there is no known algorithm that decides it. ...
Computable functions (or Turing-computable functions) are the basic objects of study in computability theory. ...
In computability theory the halting problem is a decision problem which can be informally stated as follows: Given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input. ...
In computational complexity theory, P is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. ...
In computational complexity theory, NP (Non-deterministic Polynomial time) is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine. ...
In complexity theory the class PSPACE, which equals NPSPACE by Savitchs theorem, is the set of decision problems that can be solved by a deterministic or nondeterministic Turing machine using a polynomial amount of memory and unlimited time. ...
In computational complexity theory a polynomial-time reduction is a reduction which is computable by a deterministic Turing machine in polynomial time. ...
In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space. ...
In computational complexity theory, NL is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space. ...
In computational complexity theory, P is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. ...
In computational complexity theory, NP (Non-deterministic Polynomial time) is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine. ...
In complexity theory the class PSPACE, which equals NPSPACE by Savitchs theorem, is the set of decision problems that can be solved by a deterministic or nondeterministic Turing machine using a polynomial amount of memory and unlimited time. ...
In computational complexity theory, a log-space reduction is a reduction computable by a deterministic Turing machine using logarithmic space. ...
Detailed Example The following example shows how to use reduction from the halting problem to prove that a language is undecidable. Suppose H(M, w) is the problem of determining whether a given Turing machine M halts (by accepting or rejecting) on input string w. This language is known to be undecidable. Suppose E(M) is the problem of determining whether the language a given Turing machine M accepts is empty (in other words, whether M accepts any strings at all). We show that E is undecidable by a reduction from H.
To obtain a contradiction, suppose R is a decider for E. We will use this to produce a decider S for H (which we know does not exist). Given input M and w (a Turing machine and some input string), define S(M, w) with the following behavior: S creates a Turing machine N that accepts only if the input string to N is w and M halts on input w, and does not halt otherwise. The decider S can now evaluate R(N) to check whether the language accepted by N is empty. If R accepts N, then the language accepted by N is empty, so in particular M does not halt on input w, so S can reject. If R rejects N, then the language accepted by N is nonempty, so M does halt on input w, so S can accept. Thus, if we had a decider R for E, we would be able to produce a decider S for the halting problem H(M, w) for any machine M and input w. Since we know that such an S cannot exist, it follows that the language E is also undecidable.
Notes A reduction is a preordering, that is a reflexive and transitive relation, on P(N)×P(N), where P(N) is the power set of the natural numbers. In mathematics, especially in order theory, preorders are certain kinds of binary relations that are closely related to partially ordered sets. ...
In set theory, a binary relation can have, among other properties, reflexivity or irreflexivity. ...
In mathematics, a binary relation R over a set X is transitive if it holds for all a, b, and c in X, that if a is related to b and b is related to c, then a is related to c. ...
In mathematics, given a set S, the power set (or powerset) of S, written or 2S, is the set of all subsets of S. In axiomatic set theory (as developed e. ...
In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ...
A problem is complete for a complexity class if every problem in the class reduces to that problem, and it is also in the class itself. In this sense the problem represents the class, since any solution to it can, in combination with the reductions, be used to solve every problem in the class.
Types and applications of reductions As described in the example above, there are two main types of reductions used in computational complexity, the many-one reduction and the Turing reduction. Many-one reductions map instances of one problem to instances of another; Turing reductions compute the solution to one problem, assuming the other problem is easy to solve. Many-one reduction is weaker than Turing reduction. Weaker reductions are more effective at separating problems, but they have less power, making reductions harder to design. In computational complexity theory, a many-one reduction is a reduction which converts instances of a decision problem problem A into instances of a decision problem B. We write A ≤m B or A is many-one reducible to B. If we have an algorithm N which solves instances...
In computability theory, a Turing reduction from a problem A to a problem B, named after Alan Turing, is a reduction which easily solves A, assuming B is easy to solve (Rogers 1967, Soare 1987). ...
However, in order to be useful, reductions must be easy. For example, it's quite possible to reduce a difficult-to-solve NP-complete problem like the boolean satisfiability problem to a trivial problem, like determining if a number equals zero, by having the reduction machine solve the problem in exponential time and output zero only if there is a solution. But this doesn't achieve much, because even though we can solve the new problem, performing the reduction is just as hard as solving the old problem. In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...
To meet Wikipedias quality standards, this article or section may require cleanup. ...
Therefore, the appropriate notion of reduction depends on the complexity class being studied. When studying the complexity class NP and harder classes, polynomial-time many-one reduction is used. When defining classes in the polynomial hierarchy, polynomial-time Turing reduction is used. When studying classes within P such as NC and NL, log-space reduction is used. Reduction is also used in computability theory to show whether problems are or are not solvable by machines at all; in this case, reductions are restricted only to computable functions. In computational complexity theory, NP (Non-deterministic Polynomial time) is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine. ...
In computational complexity theory a polynomial-time reduction is a reduction which is computable by a deterministic Turing machine in polynomial time. ...
In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines. ...
In computational complexity theory a polynomial-time reduction is a reduction which is computable by a deterministic Turing machine in polynomial time. ...
In complexity theory, the class NC (Nicks Class) is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. ...
In computational complexity theory, NL is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space. ...
In computational complexity theory, a log-space reduction is a reduction computable by a deterministic Turing machine using logarithmic space. ...
Computability theory is the branch of theoretical computer science that studies which problems are computationally solvable using different models of computation. ...
Computable functions (or Turing-computable functions) are the basic objects of study in computability theory. ...
See also In computability theory, many reducibility relations (also called reductions, reducibilities, and notions of reducibility) are studied. ...
In computational complexity theory, a many-one reduction is a reduction which converts instances of a decision problem problem A into instances of a decision problem B. We write A ≤m B or A is many-one reducible to B. If we have an algorithm N which solves instances...
In computability theory truth table reduction is a reduction which is stronger than many-one reduction but weaker than Turing reduction. ...
In computability theory, a Turing reduction from a problem A to a problem B, named after Alan Turing, is a reduction which easily solves A, assuming B is easy to solve (Rogers 1967, Soare 1987). ...
In computing, optimization is the process of modifying a system to make some aspect of it work more efficiently or use fewer resources. ...
References - (English) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, MIT Press, 2001, ISBN 978-0-262-03293-3
- (English) Hartley Rogers, Jr.: Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967, ISBN 978-0262680523.
- (English) Peter Bürgisser: Completeness and Reduction in Algebraic Complexity Theory, Springer, 2000, ISBN 978-3540667520.
- (English) E.R. Griffor: Handbook of Computability Theory, North Holland, 1999, ISBN 978-0444898821.
|
Feeds |
Contact