Timeline for Formal Definition of Random Reducibility
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 7, 2011 at 10:46 | comment | added | Emil Jeřábek | The Feigenbaum–Fortnow paper linked from the Wikipedia article (cs.uchicago.edu/~fortnow/papers/rsr.ps) has formal definitions on page 3. | |
| Sep 7, 2011 at 7:43 | comment | added | Bruno | You first speak about random reducibility, and then random self-reducibility. It is not the same thing! Though I think your question really is about self-reducibility. | |
| Sep 7, 2011 at 7:13 | comment | added | Kaveh | i.e. it is the same as self-reducibility, with the difference that instances in the self-reduction are chosen randomly. | |
| Sep 7, 2011 at 7:12 | comment | added | Kaveh | Here is the definition from the Wikipedia article you have linked: "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 $y_i$, then it is self-reducible (this is also known as a non-adaptive uniform self-reduction)." | |
| Sep 7, 2011 at 6:22 | history | asked | superman | CC BY-SA 3.0 |