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:
“You’ve always reminded me of a seagull, Jo. Strong and wild and fond of the wind and storms. And dreaming of flying far off to sea. And Mother always said that I was like a little cricket. Chirping contentedly on the hearth, never able to bear the thought of leaving home.”
—Victor Heerman (1893–1977)
“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 times like ours, where the growing complexity of life leaves us barely the time to read the newspapers, where the map of Europe has endured profound rearrangements and is perhaps on the brink of enduring yet others, where so many threatening and new problems appear everywhere, you will admit it may be demanded of a writer that he be more than a fine wit who makes us forget in idle and byzantine discussions on the merits of pure form ...”
—Marcel Proust (1871–1922)