It is believed that $BPP$ has no complete problems. Even for $BPP^O$ for a suitable oracle $O$ it is believed not to have complete problems, unless P=BPP. I wonder if the class MA (the randomized version of NP) has complete problems. For example, IP has complete problems (given that it is equal to PSPACE). There is a similar post asking about complexity classes with no complete problems. Here, I'm interested specifically on complete problems for MA. If the answer is positive, can you give some examples? I've tried google and the complexity zoo, but with no success.
$\begingroup$
$\endgroup$
4
-
3$\begingroup$ Actually, it is not clear that BPP has no complete language. In fact, some (many?) complexity theorists believe BPP=P, in which case BPP has a complete language! $\endgroup$– Tsuyoshi ItoCommented Aug 4, 2010 at 3:19
-
$\begingroup$ Yes, that's true. It is a very strong thig to say. I'll edit that part. Thanks $\endgroup$– Marcos VillagraCommented Aug 4, 2010 at 3:35
-
$\begingroup$ As I wrote, I do not think that it is believed that BPP has no complete language. I am afraid that there is also something wrong with the second sentence because BPP^PSPACE=PSPACE has a complete language. I do not know the situation about MA, though. At least, I believe that no MA-complete language is known, because such a characterization of MA would be a huge discovery. $\endgroup$– Tsuyoshi ItoCommented Aug 4, 2010 at 3:51
-
$\begingroup$ Yes, it actually should read "there exists" instead of "for any". $\endgroup$– Marcos VillagraCommented Aug 4, 2010 at 4:14
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
In general, for randomized classes complete problems tend to be either promise problems or approximation problems (which means they don't technically satisfy the conditions for being complete problems).
If you allow approximation problems, you can get complete problems in BPP. For example, for BPP you can ask: given a Turing machine $M$, approximate the probability that it accepts within $t$ steps on input $x$, where $t$ is polynomial in the size of the input. It's clear that you can approximate this probability with a BPP machine (using simulation), and it's also obvious that any BPP language can be reduced to this problem. Technically, this problem isn't in BPP since it's not a language (i.e., its output is not $\{0,1\}$), so it's not BPP-complete.
You can turn this into a promise problem by imposing the "promise" that the acceptance probability either be greater than $\frac{2}{3}$ or less than $\frac{1}{3}$.
These complete promise problems or approximation problems play the same role that complete problems play for non-randomized languages, and they really deserve more respect from computer scientists. For quantum computing, the natural complete problems also tend to be approximation (or promise) problems, and they have been quite useful in the theory of quantum computing.
There is a natural promise problem from quantum computing (stoquastic Hamiltonian) which is MA-complete (and not trivially so). However, I don't believe there are any languages (non-promise problems with $\{0,1\}$ answers) known to be MA-complete.
answered Aug 4, 2010 at 3:45
-
3$\begingroup$ Peter, thanks for the answer. But in general, can we ask something like: Let A and B be a complexity classes of promise problems such that $B\subseteq A$, but not known to be strictly included. If we assume $A\neq B$ then there exists a promise language $L$ which is intermediate for $A$? In other words, is there a theorem like Ladner's but for any complexity class (including randomized and quantum) considering promise languages? $\endgroup$ Commented Aug 4, 2010 at 4:26
-
1$\begingroup$ That's a really nice question. I don't know the answer. $\endgroup$ Commented Aug 4, 2010 at 11:45
$\begingroup$
$\endgroup$
3
First, it isn't "clear" that $BPP$ has no complete problems: if $TIME[2^{O(n)}]$ requires circuits of size $2^{\delta n}$ for some $\delta > 0$ then $P = BPP$, in which case $BPP$ certainly does have complete problems! (This is a famous result of Impagliazzo and Wigderson from 1998.) Also, $MA$ is not known to have complete problems, but again, under plausible circuit complexity assumptions, $NP = MA$ in which case all $NP$-complete problems are $MA$-complete too. (This is due to Klivans and van Melkebeek, and others who have weakened/changed the assumptions under which $NP=MA$ holds.) But yes, complete problems for $BPP$ and $MA$ are not currently known.
Secondly, the "promise" versions of these classes have do natural complete promise problems. (A promise problem is a pair $(\Pi_{YES}, \Pi_{NO})$ where $\Pi_{YES}, \Pi_{NO} \subseteq$ {$0,1$}$^n$, and $\Pi_{YES} \cap \Pi_{NO} = \emptyset$. The crucial point is that we do not necessarily have $\Pi_{YES} \cup \Pi_{NO} = $ {$0,1$}$^n$, so some inputs may not be considered at all in a promise problem.) For example, the following promise problem is complete for $Promise-BPP$:
Given a Boolean circuit $C$ with AND/OR/NOT gates and $n$ inputs, where you are promised that either at least 2/3 of the inputs $x \in \{0,1\}^n$ makes $C$ evaluate to $0$, or at least 2/3 of the inputs $x \in \{0,1\}^n$ make $C$ evaluate to $1$, determine which of the two is the case.
Not sure who first proved that this problem is complete, though in the literature this problem is sometimes called CAPP (for Circuit Approximation Probability Problem). One reference is Fortnow, "Comparing notions of full derandomization".
Similarly defined promise problems (with nondeterminism thrown in, naturally) are complete for $Promise-MA$.
-
1$\begingroup$ Doh! Peter rang in a minute earlier! $\endgroup$ Commented Aug 4, 2010 at 3:52
-
1
-
$\begingroup$ Ryan, yes your right, it's not clear. I've edited the post. Also, thanks for the nice example on CAPP. $\endgroup$ Commented Aug 4, 2010 at 4:27
$\begingroup$
$\endgroup$
My own favorite complete problems are promise problems for the promise problem version of SZK (Statistical Zero-Knowledge). These complete problems have played a major role in the study of SZK, and the relations among them are fascinating per se. See "On the complexity of computational problems regarding distributions (a survey)" at http://eccc.hpi-web.de/report/2011/004.
Oded
