The relationship between P vs NP problem and "Kolmogorov complexity with time" 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$
 A: Let's assume that Mark's description of the problem in the comments is correct, so that we have a fixed polynomial $P$, and the decision problem is: given $l$ and $n$, such that $l\lt \log(n)$, decide if there is some program $e$ with length $\leq l$ such that $e$ prints $n$ using time $\leq P(\log(n))$. 
This problem is in NP, because we can simply guess the program that works and check that it works in polynomial time. Note that since $n$ is an input, for NP here we are guided by polynomial time in the length of $n$. For the NP algorithm, on input $(l,n,e)$, we verify whether $e$ is a successful candidate or not, simply checking the length requirement and then running $e$ for $P(\log(n))$ steps to see whether it writes $n$ or not. If it does, we accept, and otherwise reject. The point is that this verification process is polynomial time in our input $(l,n)$. The input $(l,n)$ is acceptable in your problem if and only if there is a successful candidate $e$ making it acceptable in my algorithm, and this shows that your problem is in NP. 
