In general it is computationally undecidable to determine if a given program $p$ solves a given decision problem, and also to decide whether it does so in polynomial time. For example, consider the trivial decision problem $D$, for which the answer is always Yes. This is clearly polynomial time decidable. But to decide if a program $p$ accepts every input is a $\Pi^0_2$-complete property, which is strictly harder than the halting problem. It's definitely not decidable. To see this, consider any $\Pi^0_2$ assertion $\forall n\exists k\varphi(n,k)$, where $\varphi$ has only bounded quantifiers. The program $p$ which accepts input $n$ if it finds a $k$ for which $\varphi(n,k)$ will accept all input if and only if the statement is true, and so $\Pi^0_2$ truth reduces to accepting all input.
Meanwhile, even if a program $p$ runs in polynomial time, to decide if it accepts all input is still not computably decidable. If it were, we could design a program $p$ that pretended to halt immediately with accept on all input, unless on input $n$ it found that the decision procedure on input $p$ halted in $n$ steps saying that it accepted all input, in which case it would immediately start to reject all input. There is such a procedure by the Kleene recursion theorem, and it runs in polynomial time, but refutes the given decision procedure.
