Given an enumeration over all Turing Machine which run with increasing length, is there a ``complexity class'' which describes the complexity of determining whether a given TM satisfies the promise for MA (or QMA for a quantum computer). That is, it outputs 1 if the TM we have selected decides correct with probability p>2/3, and outputs 0 otherwise. Presumably such a task is at least (Q)MA-hard?

If, for whatever reason it is not possible to do this for TMs, can we ask the same questions about an enumeration of circuits with increasing depth/gate number?

  • 1
    $\begingroup$ The title of the question and the question seem to be different. I'm not sure I got your question, but if I did, then the same proof should work as for RP. $\endgroup$ – domotorp Dec 2 '18 at 20:44
  • $\begingroup$ Is the complexity of determining whether a given TM is in RP known? $\endgroup$ – user138901 Dec 3 '18 at 15:57
  • 1
    $\begingroup$ Yes; it is quite easy to show that it's undecidable. $\endgroup$ – domotorp Dec 3 '18 at 19:49
  • 1
    $\begingroup$ The problem is (sticking to RP, for simplicity) that your estimate what you get after many runs might be very close to 1/2. You cannot tell if it's above or below. And as you right the statement does follow from Rice, as there is no 'otherwise' - Rice holds also if you are allowed to run the code. $\endgroup$ – domotorp Dec 6 '18 at 8:59
  • 1
    $\begingroup$ Yes, what you write is a method for any $x$ of size $n$ to check if the TM works properly. The problem is checking whether it works properly for every $x$ for every $n$. $\endgroup$ – domotorp Mar 6 '19 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.