Hacker News new | past | comments | ask | show | jobs | submit login

In another paper they imply that the time bound also effectively bounds the solvability of the one-way function. So, without the bound you say "can Kolmogorov complexity be calculated?", which implies "given infinite time can you solve this one-way function?" With the bound, it's saying "given this time limit to calculating Kolmogorov complexity, can the one-way function be solved within a directly related time limit?" The assumption is that practically speaking it doesn't matter if the one-way function can be solved in millions of eons, so a corresponding time bound is acceptable.



Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: