Verifier for A_tm in polynomial time - how to formally prove it does not exist?

How would you formally prove the non-existance of a polynomial time verifier for $$A_\mathrm{TM}$$?

I mean we can't just say that in order to read a certain certificate we need more than poly-time because we need to prove it for any possible certificate. What would be the correct proof ?

• I thought about proof by contradiction- if we do have a polytime verifier then Atm is in Np --> then it has a non-deterministic machine that decides in in polyitme -->it has a determinsitic TM that decides in 2^(polytime) --> Atm is decidable -->contradiction Commented Dec 21, 2018 at 11:49
• This argument seems completely fine. Perhaps you'd like to answer your own question? Commented Dec 21, 2018 at 15:08

Suppose by contradiction $$A_\mathrm{TM}$$ has polytime verifier $$\Longrightarrow$$ $$A_\mathrm{TM}$$ is in NP $$\Longrightarrow$$ $$A_\mathrm{TM}$$ is decideable by some non-deterministic TM in polytime $$\Longrightarrow$$ $$A_\mathrm{TM}$$ is dcidiable by some deterministic $$2^{\mathrm{polytime}}$$ TM $$\Longrightarrow$$ $$A_\mathrm{TM}$$ is decidable $$\Longrightarrow$$ contradiction.