Polynomial-time reduction
- Polynomial-time reduction
In computational complexity theory a polynomial-time reduction is a reduction which is computable by a deterministic Turing machine in polynomial time. If it is a many-one reduction, it is called a polynomial-time many-one reduction, polynomial transformation, or Karp reduction. If it is a Turing reduction, it is called a polynomial-time Turing reduction or Cook reduction.
Polynomial-time reductions are important and widely-used because they are powerful enough to perform many transformations between important problems, but still weak enough that polynomial-time reductions from problems in NP or co-NP to problems in P are considered unlikely to exist. This notion of reducibility is used in the standard definitions of several complete complexity classes, such as NP-complete, PSPACE-complete and EXPTIME-complete.
Within the class P, however, polynomial-time reductions are inappropriate, because any problem in P can be polynomial-time reduced (both many-one and Turing) to any non-trivial problem in P. Thus, for classes within P such as L, NL, NC, and P itself, log-space reductions are used instead.
If a problem has a Karp reduction to a problem in NP, this shows that the problem is in NP. Cook reductions seem to be more powerful than Karp reductions; for example, any problem in co-NP has a Cook reduction to any NP-complete problem, whereas any problems that are in co-NP - NP (assuming they exist) will not have Karp reductions to any problem in NP. While this power is useful for designing reductions, the downside is that certain classes such as NP are not known to be closed under Cook reductions (and are widely believed not to be), so they are not useful for proving that a problem is in NP. However, they are useful for showing that problems are in P and other classes that are closed under such reductions.
Wikimedia Foundation.
2010.
Look at other dictionaries:
Time complexity — In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O… … Wikipedia
Reduction (complexity) — Example of a reduction from a boolean satisfiability problem to a vertex cover problem. Blue vertices form a vertex cover which corresponds to truth values. In computability theory and computational complexity theory, a reduction is a… … Wikipedia
Reduction (recursion theory) — In computability theory, many reducibility relations (also called reductions, reducibilities, and notions of reducibility) are studied. They are motivated by the question: given sets A and B of natural numbers, is it possible to effectively… … Wikipedia
Log-space reduction — In computational complexity theory, a log space reduction is a reduction computable by a deterministic Turing machine using logarithmic space. Conceptually, this means it can keep a constant number of pointers into the input, along with a… … Wikipedia
Many-one reduction — In computability theory and computational complexity theory, a many one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem. Reductions are thus used to measure the relative… … Wikipedia
Chromatic polynomial — All nonisomorphic graphs on 3 vertices and their chromatic polynomials, clockwise from the top. The independent 3 set: k3. An edge and a single vertex: k2(k − 1). The 3 path: k(k − 1)2. The 3 clique … Wikipedia
PTAS reduction — In computational complexity theory, a PTAS reduction is a reduction that is often used to perform reductions between solutions to optimization problems. It preserves the property that a problem has a polynomial time approximation scheme (PTAS)… … Wikipedia
Lenstra–Lenstra–Lovász lattice basis reduction algorithm — The Lenstra–Lenstra–Lovász lattice basis reduction (LLL) is a polynomial time lattice reduction algorithm invented by Arjen Lenstra, Hendrik Lenstra and László Lovász. Given as input d lattice basis vectors with n dimensional integer coordinates… … Wikipedia
Turing reduction — In computability theory, a Turing reduction from a problem A to a problem B, named after Alan Turing, is a reduction which solves A, assuming B is already known (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to … Wikipedia
L-reduction — is a transformation of optimization problems which keeps the approximability features. L reductions in studies of approximability of optimization problems play a similar role to that of polynomial reductions in the studies of computational… … Wikipedia
