Many-one Reductions With Resource Limitations
Many-one reductions are often subjected to resource restrictions, for example that the reduction function is computable in polynomial time or logarithmic space; see polynomial-time reduction and log-space reduction for details.
Given decision problems A and B and an algorithm N which solves instances of B, we can use a many-one reduction from A to B to solve instances of A in:
- the time needed for N plus the time needed for the reduction
- the maximum of the space needed for N and the space needed for the reduction
We say that a class C of languages (or a subset of the power set of the natural numbers) is closed under many-one reducibility if there exists no reduction from a language in C to a language outside C. If a class is closed under many-one reducibility, then many-one reduction can be used to show that a problem is in C by reducing a problem in C to it. Many-one reductions are valuable because most well-studied complexity classes are closed under some type of many-one reducibility, including P, NP, L, NL, co-NP, PSPACE, EXP, and many others. These classes are not closed under arbitrary many-one reductions, however.
Read more about this topic: Many-one Reduction
Famous quotes containing the words reductions, resource and/or limitations:
“The work was like peeling an onion. The outer skin came off with difficulty ... but in no time you’d be down to its innards, tears streaming from your eyes as more and more beautiful reductions became possible.”
—Edward Blishen (b. 1920)
“If there is nothing new on the earth, still the traveler always has a resource in the skies. They are constantly turning a new page to view. The wind sets the types on this blue ground, and the inquiring may always read a new truth there.”
—Henry David Thoreau (1817–1862)
“... art transcends its limitations only by staying within them.”
—Flannery O’Connor (1925–1964)