# Complexity of enumerating over promise problems and circuits?

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?

• 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. – domotorp Dec 2 '18 at 20:44
• Is the complexity of determining whether a given TM is in RP known? – user138901 Dec 3 '18 at 15:57
• Yes; it is quite easy to show that it's undecidable. – domotorp Dec 3 '18 at 19:49
• 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? – user138901 Dec 6 '18 at 1:06
• 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. – domotorp Dec 6 '18 at 8:59