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)
“In a world which furnishes so many employments which are useful, and so many which are amusing, it is our own fault if we ever know what ennui [boredom] is, or if we are ever driven to the miserable resource of gaming, which corrupts our dispositions, and teaches us a habit of hostility against all mankind.”
—Thomas Jefferson (1743–1826)
“To note an artist’s limitations is but to define his talent. A reporter can write equally well about everything that is presented to his view, but a creative writer can do his best only with what lies within the range and character of his deepest sympathies.”
—Willa Cather (1876–1947)