Computational depth and application of resource bounded Kolmogorovo complexity to security

4 dezembro 2014, 17:30 Paulo Alexandre Carreira Mateus

Time bounded and space bounded Kolmogorov complexity classes.
Proof that size of description is an independent parameter than time and space.
Computational depth a measure of information usefulness.
Examples of deep objects.
Proof that the number of deep strings increases exponentially with size.
Computational depth of average case complexity.
Applications of resourced-bound Kolmogorov complexity to cryptography. The case of one-way functions.