Time bounded Kolmogorov complexity is the smallest amount of data that can output a given piece of data within a given amount of time.

For this example, Kolmogorov complexity is defined as being able to output the result in an amount of time linearly proportional to the file size. For example, a 64 bit piece of data is allowed twice as much time as a 32 bit piece of data.

Note: I say it is EXPTIME because although you can check the individual result in polynomial/linear time, but you have to check the results below to see if they also output that result in that timeframe. I am not talking about a specific language.

  • 2
    $\begingroup$ (1) Put your question in the question, not in the title. (2) It’s not clear to me what the computation problem is, really. What, exactly, is the input? $\endgroup$ – Emil Jeřábek supports Monica Jan 12 at 7:12
  • $\begingroup$ A string that is being inputted into a given language to output the shortest string that can be ran as a program in the other language. $\endgroup$ – Number File Jan 12 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.