Given a Turing Complete Language, the optimization problem would be: Given inputs x and S, where x is a finite binary string and S is a limit on steps, find the shortest program in that TC language that outputs the string x in less than or equal to S steps. (With S being in unary.)

My question is how approximable this definition of time-bounded KC is in terms of the NPO classes such as PTAS, APX, log APX, and so on.

I've been searching and have only been able to find info on KC itself and little info on resource-bounded KC as a decision or optimization problem.

  • $\begingroup$ Is S in unary? ​ (If no, then the problem is not obviously in NPO.) ​ ​ ​ ​ $\endgroup$ – user12859 Jun 12 '16 at 6:07
  • $\begingroup$ Steps can't be negative so it's greater than or equal to 1. $\endgroup$ – Chessmanguy Jun 12 '16 at 6:49
  • $\begingroup$ What's the significance of it being in unary? $\endgroup$ – Chessmanguy Jun 12 '16 at 7:03
  • $\begingroup$ See this question and its answers. ​ ​ $\endgroup$ – user12859 Jun 12 '16 at 7:05
  • $\begingroup$ Very interesting distinction, for the purpose of my question then yes S is in unary. $\endgroup$ – Chessmanguy Jun 12 '16 at 8:00

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.