15

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?

Niel de Beaudrap
  • 8,821
  • 31
  • 70
  • 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…. – Tsuyoshi Ito Jan 31 '12 at 19:14
  • 1
    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. – Emil Jeřábek Jan 31 '12 at 19:25
  • @Emil: I understand that if “high probability” is 1/poly, but is it possible to increase that probability to, say, a constant? – Tsuyoshi Ito Jan 31 '12 at 19:35
  • Fair enough, that’s actually a rather small probability. I don’t know how to make it a constant. – Emil Jeřábek Jan 31 '12 at 19:50
  • @Emil: I have just remembered a related paper by Kabanets and Watanabe (see related question). – Tsuyoshi Ito Feb 04 '12 at 01:03
  • 1
    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. – Tsuyoshi Ito Feb 05 '12 at 13:10
  • @TsuyoshiIto: Good point. I definitely want to work with public-coin protocols. I'm aware that the two regimes are meant to give rise to the same class (and that this is essentially due to the fact that $\mathsf{AM}[k] = \mathsf{AM}$ for any constant $k \geqslant 2$), but haven't studied precisely the connection. Do you suspect that imposing unique valid answers might make the equivalence non-trivial, or perhaps false? – Niel de Beaudrap Feb 06 '12 at 15:51
  • A proof of AM[2]=IP[2] is usually done in two steps as IP[2]⊆AM[4]⊆AM[2]. I think that both steps introduce nonunique answers with at least exponentially small probability and I cannot see how to recover the unique-answer property with certainty, so I doubt that public and private coins are equivalent as long as you want the unique-answer property with certainty. But if you allow nonunique answers with exponentially small probability, I do not immediately see a point where the proof does not go through (but this does not mean much except that I am not very familiar with the proofs). – Tsuyoshi Ito Feb 07 '12 at 02:35
  • @TsuyoshiIto: I suppose your remarks correspond to something like AM = BP•NP = BP•PromiseUP, while my question amounts to whether AM ⊆ coR•PromiseUP. So I imagine that the proofs do carry through in the way you suggest, with exponentially-small error, to provide the already known containment. – Niel de Beaudrap Feb 07 '12 at 16:47

1 Answers1

1

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.

Mark S
  • 1,083
  • 6
  • 20