# 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
• 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
• 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$. – domotorp Mar 6 at 19:26