Random Self-reducibility

Random Self-reducibility

Random self-reducibility (RSR) is the rule that 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.

Read more about Random Self-reducibility:  Definition, Application in Cryptographic Protocols, Examples, Consequences

Famous quotes containing the word random:

    “It is a secret from nobody that the famous random event is most likely to arise from those parts of the world where the old adage “There is no alternative to victory” retains a high degree of plausibility.”
    —Hannah Arendt (1906–1975)