Random Self-Reducibility

Herausgegeben:Surhone, Lambert M.; Tennoe, Mariam T.; Henssonow, Susan F.

• Broschiertes Buch

Produktbeschreibung

Please note that the content of this book primarily consists of articles available from Wikipedia or other free sources online. Random self-reducibility (RSR): A good algorithm for the average case implies a good algorithm for the worst case. RSR is the ability to solve all instances of a problem by solving a large fraction of the instances.If a function f evaluating any instance x can be reduced in polynomial time to the evaluation of f on one or more random instances yi, then it is self-reducible (this is also known as a non-adaptive uniform self-reduction). In a random self-reduction an arbitrary worst-case instance x in the domain of f is mapped to a random set of instances y1, ..., yk. This is done so that f(x) can be computed in polynomial time, given the coin-toss sequence from the mapping, x, and f(y1), ..., f(yk). Therefore, taking the average with respect to the induced distribution on yi, the average-case complexity of f is the same (within polynomial factors) as the worst-case randomized complexity of f.

Produktdetails

• Verlag: Betascript Publishing
• Seitenzahl: 88
• Englisch
• Abmessung: 220mm
• ISBN-13: 9786131366932
• ISBN-10: 6131366934
• Artikelnr.: 31725080