Is $nHALT$ undecidable even if $M$ halts on input $w$ in finite steps

Question

If we have the language

$nHALT=\{<M,w,n>;$ $M$ halts on input $w$ in less than $n$ steps$\}$

Is this language also undecidable in the same way that $HALT$ is undecidable? And if so, $nHALT\notin P$, right?

Answer 1

This language is obviously decideable, just emulate $M$ on $w$ and see whether it halted within $n$ steps or not...

Now, to whether $nHALT\in P$ or $nHALT\notin P$. The length of $n$ here is logarithmic to its "value" (assuming that $\Sigma$ here is not unary). Thus, the number of steps we will need to emulate would be exponential in its size! I dont see a polynomial time algorithm for that, so I assume it's probably not in P. But I have not proven that (just gave intuition on why it could be the case), and there is also a chance that showing that is equivalent to some open problem (maybe somehow you could prove its $\mathcal {NP-Complete}$?)