“Given an algorithm, decide whether it runs in polynomial time” is this problem in NP?

Question

This problem is not decidable (reducible to halting problem) but is semi-decidable and therefor verifiable (as those two definitions are equivalent: How to prove semi-decidable = verifiable?).

However, is this problem poly-time verifiable?

A decision problem $P$ is poly time verifiable iff there is an algorithm 𝑉 called verifier such that if $P(w)=$𝑌𝐸𝑆 then there is a string $c$ s.t. $𝑉(w,c)=$𝑌𝐸𝑆, if $P(w)=𝑁𝑂$ then for all strings $c$, $𝑉(w,c)=$𝑁𝑂 and V runs in $O(w^{k})$ for some constant $k$ for all inputs $w$.

Answer 1

No. If the problem was polynomial-time verifiable, it would be solvable in exponential time, and thus decidable; but we already know that is not decidable.

Why in exponential time? Because $V$ runs in time $|w|^k$, it can read at most $|w|^k$ bits of the input. So, it suffices to enumerate all possible strings $c$ of length at most $|w|^k$, and run $V$ on each of them. The running time will be about $2^{|w|^k}$, which is finite and thus enough to make the original problem decidable.