3 ms·
The bit I don't get: The time-bounded Kolmogorov complexity is an approximation. But it seems to be being used to prove that cryptography based on one-way func
by denton-scratch 5y ago
The bit I don't get:
The time-bounded Kolmogorov complexity is an approximation. But it seems to be being used to prove that cryptography based on one-way functions is/isn't possible.
It's not obvious to this grandstanding ignoramus that the approximation taints the proof; nor that it doesn't. I just prefer proofs that don't include approximations.
- pishpash 5y agoIt's not an approximation, it defines a variant version of the problem that makes sense in the context of practical computation.
- derbOac 5y agoIn 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.