4 ms·
Well, thanks for the Wikipedia link. It says average complexity is very important for sorting algorithms and cryptographic one-way functions. I found especially
by cubefox 4y ago
Well, thanks for the Wikipedia link. It says average complexity is very important for sorting algorithms and cryptographic one-way functions. I found especially this part remarkable:
> Note that it is not desirable for the candidate function to be NP-complete since this would only guarantee that there is likely no efficient algorithm for solving the problem in the worst case; what we actually want is a guarantee that no efficient algorithm can solve the problem over random inputs (i.e. the average case). In fact, both the integer factorization and discrete log problems are in NP ∩ coNP, and are therefore not believed to be NP-complete.
Regarding this question:
> How do you take the uniform distribution over matrices over the (infinite) real numbers?
Well, naively, how about screw the real numbers and just take the uniform distribution over the, say, 64 bit floats, which are conveniently finite? At least if we use those in practice? But I guess this goes in the direction of "Because in the real world, your distribution will rarely be uniform", since the 64 bit floats are a subset of the real numbers, and any uniform distribution over the former is equivalent to a non-uniform distribution over the latter (probability 0 to any reals not in the 64 bit floats).
- abdullahkhalids 4y ago64-bit floats are a finite set. The solution of problems where the real numbers are replaced by the finite set is sometimes easier, but often much more difficult. The reason is that you can't do calculus over finite fields. For instance, taking the inverse of the natural log is efficient, but the inverse of the discrete log is a hard problem, and hence is used in cryptographic algorithms. Complexity theory is a very subtle science.
- cubefox 4y agoNontheless, in practice most algorithms have a limited range of inputs, in which case there should be no problem with infinity?