1
$\begingroup$

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 ?

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – caffein
    Commented Dec 21, 2018 at 11:49
  • 1
    $\begingroup$ This argument seems completely fine. Perhaps you'd like to answer your own question? $\endgroup$ Commented Dec 21, 2018 at 15:08

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.