15
$\begingroup$

Preamble.

The complexity class AM are those problems which can be solved by a two-round interactive proof system between a prover "Merlin" and a verifier "Arthur". A problem — which tests some property of an object X — is in AM if:

  • For YES instances, for a random "challenge" message (of polynomial length) Arthur generates, with high probability Merlin can formulate a (polynomial length) reply which Arthur can use as evidence that X has the property;

  • For NO instances, for a random challenge message Arthur generates, with high probability Merlin cannot formulate any reply which can be used as evidence for the property being tested for on X.

— The class described doesn't change if we require Merlin to give a useful answer not just with high probability, but for any challenge that Arthur may issue; we might say in this case that we require Merlin's answer always to be valid for YES instances, and what Arthur tests is the validity of the answer. So if Merlin ever produces an invalid response, Arthur knows that the problem instance is a NO instance. This is the setting I'd prefer to consider.

An example is Graph Non-Isomorphism: given graphs G and H with the same set of vertex labels, Arthur can randomly select one of the graphs and produce a "scrambled" version F by permuting its vertex labels, sending a presentation of it to Merlin. If the two graphs are non-isomorphic, Merlin can identify which of G or H Arthur chose by determining whether F ≅ G or F ≅ H, and can respond by identifying which of the two F is isomorphic to. If the two graphs G and H are isomorphic, however, Merlin cannot distinguish which graph F came from, and any answer he gives can only be correct by chance. Thus, for YES instances Merlin can always send a valid response to any challenge; for NO instances any response which Merlin might send will be with high probability invalid.

In the above problem, not only does there exist a valid response that Merlin can issue to Arthur for each challenge, but in fact there is a unique valid response: i.e. indicate which of G or H Arthur chose, given that this can be determined by identifying which is isomorphic to F.

Question.

Does imposing a constraint along these lines — that for YES instances, for any challenge Arthur might send, there is exactly one valid response for Merlin — yield a more restrictive class, in the sense of yielding a class which is not known to equal AM?

$\endgroup$
  • $\begingroup$ Before considering whether it is equal to AM or not, I even fail to see how to prove that NP is contained in your class…. $\endgroup$ – Tsuyoshi Ito Jan 31 '12 at 19:14
  • 1
    $\begingroup$ If we require Merlin to have one valid response only with high probability, then the class does contain NP (and, I guess, all of AM): we can make Arthur perform the Valiant–Vazirani reduction to Unique-SAT. $\endgroup$ – Emil Jeřábek supports Monica Jan 31 '12 at 19:25
  • $\begingroup$ @Emil: I understand that if “high probability” is 1/poly, but is it possible to increase that probability to, say, a constant? $\endgroup$ – Tsuyoshi Ito Jan 31 '12 at 19:35
  • $\begingroup$ Fair enough, that’s actually a rather small probability. I don’t know how to make it a constant. $\endgroup$ – Emil Jeřábek supports Monica Jan 31 '12 at 19:50
  • 1
    $\begingroup$ Are you considering public-coin protocols or private-coin protocols? From the definition, it seems that you are thinking of public-coin protocols, but the protocol for graph non-isomorphism which you described is not a public-coin protocol. $\endgroup$ – Tsuyoshi Ito Feb 5 '12 at 13:10
1
$\begingroup$

Koiran's paper Hilbert's Nullstellensatz is in the Polynomial Hierarchy provides a public-coin Arthur-Merlin protocol for establishing that a system of $m$ equations on $n$ unknowns has a solution in $\mathbb{C}^n$, contingent on the Generalized Riemann Hypothesis. Here Merlin finds a prime $p$ with $H(p)=0$ for some random hash $H$, along with a solution $(a_0,a_1,\cdots, a_n)$ to each of the $m$ equations $\bmod p$.

If the system of equations has no solution $\bmod p$, then there will only be a finite number of $p$ modulo which a solution exists. If the system does have a solution $\bmod p$, then unconditionally there will be an positive density of $p$ with a solution, and the GRH allows that the $p$ with a solution are "equidistributed" in some sense, such that Merlin gets a win.

Although Koiran gives an example of a solvable system where the density of $p$ is exponentially small, Koiran suggests that if the system is solvable in $\mathbb{C}^n$, then in most cases there will be a large number of $p$ (and a large number of $a$); indeed about $1-1/e$ primes should have a solution IIRCC.

Thus, in the above problem, not only does there exist a valid response that Merlin can issue to Arthur for each challenge, but in fact there could be a large number of valid responses.

Distinguishing the easy systems of equations with solutions modulo many $p$ from the hard systems of equations with a few or only one $p$ seems to require determining properties of a Galois group of the system of equations.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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