12
$\begingroup$

I'm curious about whether there are any complete problems in the Arthur-Merlin complexity class. Graph Non-Isomorphism (GNI) seems to be the canonical example of a problem in AM, but it's probably not a complete one.

I suppose I'm also wondering if a "complete" problem is well-defined for AM. Since AM = BP.NP, it seems the go to "reduction" to AM relies on randomized reductions to 3SAT rather than the Karp reductions we use for deterministic complexity classes. So maybe since Karp reductions have no error, "Karp reducing to an AM problem" doesn't really have any meaning, thus invalidating the usual notion we use of a "complete" problem?

$\endgroup$
1

1 Answer 1

1
$\begingroup$

Since AM = BP.NP, it seems the go to "reduction" to AM relies on randomized reductions to 3SAT rather than the Karp reductions we use for deterministic complexity classes.

This is a wrong intuition. Regardless of how you define your complexity class $\mathbb{C}$, if there exists any problem $\mathrm{A}\in \mathbb{C}$ such that for every problem $\mathrm{B}\in \mathbb{C}$, you have $\mathrm{B} \leq_p \mathrm{A}$, then $\mathrm{A}$ is a many-one complete problem of $\mathbb{C}$.

In fact, even a problem that is complete by randomized reductions for $\mathrm{AM}$ is not known. Put in other word, it seems very hard to just pin down any particular decision problem in $\mathrm{AM}$ so that we can have some non-trivial reduction from other problems known to be in $\mathrm{AM}$.

See mathoverflow.net/questions/34469 and cstheory.stackexchange.com/questions/1233; in short, the definition of AM relies on a promise, and this makes it tricky to define a reduction. – sdcvvc

That is one of the obstacles on the way to find a complete problem for $\mathrm{AM}$. This is also applicable to $\mathrm{BPP}$, $\mathrm{RP}$, $\mathrm{co}$-$\mathrm{RP}$, $\mathrm{ZPP}$. These classes requires the poly-time probabilistic Turing machine to have bounded error probability on all instances. The situation is much easier for $\mathrm{PP}$, this class does not put any requirement on the error probability, whichever result has the higher probability is the answer of the machine so we can easily catch a complete problem for it, namely $\mathrm{MAJ}$-$\mathrm{SAT}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.