[O45] Given a string x of length n decide if x can be generated from a program of length k in time t(n). Is this question NP complete assuming t(n) is polynomial?

Comments. If this question can be answered in polynomial time for t(n)

a polynomial, then one can run the algorithm for k = 1,...,n in polynomial time. Therefore the question implies whether Ct

(x) (and Kt

(x))

can be computed in polynomial time. In its turn this implies that for every x we can compute Ct

(x) ≥ n (and Kt

(x) ≥ n)) in polynomial time.