Timeline for If a one-way functions (OWF) exist, then there exits a OWF that is computable in quadratic running time by a padding argument
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 8, 2014 at 17:04 | comment | added | Charlie Parker | Your example still proved extremely useful because it made it extremely clear for me what the point was (which I had a hard time appreciating because of the looseness of the bound that was bothering me). Thanks! :) | |
| Jan 8, 2014 at 7:48 | vote | accept | Charlie Parker | ||
| Jan 8, 2014 at 6:44 | comment | added | D.W.♦ | @CharlieParker, ahh, OK, I see what you mean. I edited my answer. I agree with your reasoning. I don't think your reasoning is incorrect. | |
| Jan 8, 2014 at 6:44 | history | edited | D.W.♦ | CC BY-SA 3.0 |
added 257 characters in body
|
| Jan 7, 2014 at 1:16 | comment | added | Charlie Parker | (by unsure, I guess I meant, it made me question). | |
| Jan 7, 2014 at 0:37 | comment | added | Charlie Parker | Your answer made me unsure whether I understand what is the length of the input to f'. I defined in my question what I thought the length of the input is to f' and tried justifying why it ran in linear time wrt to that input, was that not correct? Also, I did read and understand ur example and it makes sense. Unfortunately, I am still not sure why my original approach is still incorrect. | |
| Jan 6, 2014 at 7:54 | history | answered | D.W.♦ | CC BY-SA 3.0 |