Resource-Bounded Complexity

Recursion theory has a resource-bounded version in computational complexity theory. Similarly, Kolmogorov complexity has resource-bounded Kolmogorov complexity (also known as generalized Kolmogorov complexity). Several authors suggested early on the possibility of restricting the power of the device used to (de)compress strings. Says Kolmogorov:

“The concept discussed ...does not allow for the ‘difficulty’ of preparing a program

p

for passing from an object

x

to an object

y

. [... some] object permitting a very simple program, i.e., with very small complexity

K

(

x

) can be restored by short programs only as the result of computations of a thoroughly unreal nature. [... this concerns] the relationship between the necessary complexity of a program and its permissible difficulty

t

. The complexity

K

(

x

) that was obtained [before] is, in this case, the minimum of

K

t

(

x

) on the removal of the constraints on

t

.”