Let $P$ - polynomial($P(x) \ge x$), $n \in \mathbb{N}$, $l < log(n)$.

Problem1: "Is there program with length $\le l$ that print $n$ by using $\le P(log(n))$ time?"

Is it Problem1 $\in NP$-complete?

Now I'll explain why I think that this problem hasn't a polynomial solution.

Define "Kolmogorov complexity with time" $K(P, n)$ as minimal program that work $\le P(log(n))$ time.

Kolmogorov complexity is not a computable function. A natural analogue of this statement:

"Kolmogorov complexity with time" $\notin P$ (1)

It is easy to see, that if Problem1 $\in P$ than "Kolmogorov complexity with time" $\in P$. So, if Problem1 $\in NP$-complete than (1) $\iff P \not=NP$