Is $\{\langle M \rangle \mid \exists P \;\text{(p is polynom)}\; \forall w\; \text{M(w) halt with less than p(|w|) steps}\} \in RE$?

Question

Is $L=\{\langle M \rangle \mid \exists P \;\text{(p is polynom)}\; \forall w\; \text{M(w) halt with less than p(|w|) steps}\} \in RE$?

I can prove that $L \notin coRE$, but I don't know what to do about $RE$...

The question is very similar to the question here, but this problem looks really harder, and I have no idea how to do it, since there is no finite set that I can check single polynom.

Answer 1

Hint: For some $M_0$ and $w_0$ consider the function

$$ f(n) = \begin{cases} \bot & \text{ if $M_0(w_0)$ halts in exactly $n$ steps} \\ 0 & \text{otherwise} \end{cases} $$

Does $L$ contain the machine that computes $f$ in the straightforward way?