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
  • $\begingroup$ Surely you could just run the problem multiple times, estimate the acceptance probability, and find the answer? Am I missing something? Or are you assuming that we aren't able to do this (I'm interested in both cases). I suppose otherwise we can apply Rice's theorem? $\endgroup$ – user138901 Dec 6 '18 at 1:06
  • $\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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.