Strong Reductions in Computational Complexity
The strong reductions listed above restrict the manner in which oracle information can be accessed by a decision procedure but do not otherwise limit the computational resources available. Thus if a set A is decidable then A is reducible to any set B under any of the strong reducibility relations listed above, even if A is not polynomial-time or exponential-time decidable. This is acceptable in the study of recursion theory, which is interested in theoretical computability, but it is not reasonable for computational complexity theory, which studies which sets can be decided under certain asymptotical resource bounds.
The most common reducibility in computational complexity theory is polynomial-time reducibility; a set A is polynomial-time reducible to a set B if there is a polynomial-time function f such that for every n, n is in A if and only if f(n) is in B. This reducibility is, essentially, a resource-bounded version of many-one reducibility. Other resource-bounded reducibilities are used in other contexts of computational complexity theory where other resource bounds are of interest.
Read more about this topic: Reduction (recursion Theory), Reductions Stronger Than Turing Reducibility
Famous quotes containing the words strong, reductions and/or complexity:
“There is only one vice, which may be found in life with as strong features, and as high a colouring as needs be employed by any satyrist or comic poet; and that is AVARICE.”
—David Hume (1711–1776)
“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)
“The price we pay for the complexity of life is too high. When you think of all the effort you have to put in—telephonic, technological and relational—to alter even the slightest bit of behaviour in this strange world we call social life, you are left pining for the straightforwardness of primitive peoples and their physical work.”
—Jean Baudrillard (b. 1929)