<p>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?</p>

<p>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?</p>

CC BY-SA 4.0
2018-12-02T20:44:37.570Z
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
CC BY-SA 4.0
2018-12-03T15:57:53.533Z
Is the complexity of determining whether a given TM is in RP known?
Hans Schmuber
CC BY-SA 4.0
2018-12-03T19:49:53.887Z
Yes; it is quite easy to show that it's undecidable.
domotorp
CC BY-SA 4.0
2018-12-06T01:06:43.150Z
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?
Hans Schmuber
CC BY-SA 4.0
2018-12-06T08:59:02.490Z
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
CC BY-SA 4.0
2019-03-06T12:33:41.067Z
@domotorp surely if I have a TM that is guaranteed to run for time $poly(n)$, then the output probabilities are discretised in steps of $2^{poly(n)}$. Thus I can use a TM that runs for exponentially longer to run the same problem, but then amplify with exponentially more time to determine which size of 1/2 the original TM output was?
Hans Schmuber
CC BY-SA 4.0
2019-03-06T19:26:52.933Z
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
<cc.complexity-theory><complexity-classes><quantum-computing><promise-problems><enumeration>
Complexity of enumerating over promise problems and circuits?
Hans Schmuber
# Complexity of enumerating over promise problems and circuits?

(Asked by: username_0 on 2018-11-30)

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?

**Tags:** cc.complexity-theory, complexity-classes, quantum-computing, promise-problems, enumeration

> **Comments:**
> **username_1**: 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.  
> **username_0**: Is the complexity of determining whether a given TM is in RP known?  
> **username_1**: Yes; it is quite easy to show that it's undecidable.  
> **username_0**: 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?  
> **username_1**: 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.  
> **username_0**: @username_1 surely if I have a TM that is guaranteed to run for time $poly(n)$, then the output probabilities are discretised in steps of $2^{poly(n)}$. Thus I can use a TM that runs for exponentially longer to run the same problem, but then amplify with exponentially more time to determine which size of 1/2 the original TM output was?  
> **username_1**: 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$.  

---

## 0 answers

