<p>Koiran's paper <a href="https://www.sciencedirect.com/science/article/pii/S0885064X96900199" rel="nofollow noreferrer">Hilbert's Nullstellensatz is in the Polynomial Hierarchy</a> provides a public-coin Arthur-Merlin protocol for establishing that a system of <span class="math-container">$m$</span> equations on <span class="math-container">$n$</span> unknowns has a solution in <span class="math-container">$\mathbb{C}^n$</span>, contingent on the Generalized Riemann Hypothesis.  Here Merlin finds a prime <span class="math-container">$p$</span> with <span class="math-container">$H(p)=0$</span> for some random hash <span class="math-container">$H$</span>, along with a solution <span class="math-container">$(a_0,a_1,\cdots, a_n)$</span> to each of the <span class="math-container">$m$</span> equations <span class="math-container">$\bmod p$</span>.</p>

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

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

<p>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 <em>large</em> number of valid responses.</p>

<p>Distinguishing the easy systems of equations with solutions modulo many <span class="math-container">$p$</span> from the hard systems of equations with a few or only one <span class="math-container">$p$</span> seems to require determining properties of a Galois group of the system of equations.</p>

CC BY-SA 4.0
2019-03-23T18:50:20.527Z
2019-03-23T18:50:20.527Z
Mark S
<p><strong>Preamble.</strong></p>

<p>The complexity class <a href="http://en.wikipedia.org/wiki/Arthur%E2%80%93Merlin_protocol#AM"><strong>AM</strong></a> are those problems which can be solved by a two-round interactive proof system between a prover "Merlin" and a verifier "Arthur". A problem &mdash; which tests some property of an object <em>X</em> &mdash; is in <strong>AM</strong> if:</p>

<ul>
<li><p>For <em>YES</em> 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 <em>X</em> has the property;</p></li>
<li><p>For <em>NO</em> 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 <em>X</em>.</p></li>
</ul>

<p>&mdash; The class described doesn't change if we require Merlin to give a useful answer not just with high probability, but for <em>any</em> challenge that Arthur may issue; we might say in this case that we require Merlin's answer always to be <em>valid</em> for <em>YES</em> 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 <em>NO</em> instance. This is the setting I'd prefer to consider.</p>

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

<p>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 <em>unique</em> valid response: <em>i.e.</em>&nbsp;indicate which of <em>G</em> or <em>H</em> Arthur chose, given that this can be determined by identifying which is isomorphic to <em>F</em>.</p>

<p><strong>Question.</strong></p>

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

CC BY-SA 3.0
2012-01-31T19:14:54.983Z
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
CC BY-SA 3.0
2012-01-31T19:25:53.253Z
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
CC BY-SA 3.0
2012-01-31T19:35:26.533Z
@Emil: I understand that if “high probability” is 1/poly, but is it possible to increase that probability to, say, a constant?
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-31T19:50:45.943Z
Fair enough, that’s actually a rather small probability. I don’t know how to make it a constant.
Emil Jeřábek
CC BY-SA 3.0
2012-02-04T01:03:22.960Z
@Emil: I have just remembered a related paper by Kabanets and Watanabe ([see related question](http://cstheory.stackexchange.com/questions/7552/derandomizing-valiant-vazirani)).
Tsuyoshi Ito
CC BY-SA 3.0
2012-02-05T13:10:00.353Z
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
CC BY-SA 3.0
2012-02-06T15:51:16.207Z
@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
CC BY-SA 3.0
2012-02-07T02:35:18.187Z
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
CC BY-SA 3.0
2012-02-07T16:47:46.113Z
@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
<cc.complexity-theory><interactive-proofs><unique-solution>
Does requiring uniqueness of valid answers for Merlin limit the power of Arthur-Merlin protocols?
Niel de Beaudrap
# Does requiring uniqueness of valid answers for Merlin limit the power of Arthur-Merlin protocols?

(Asked by: username_0 on 2012-01-31)

**Preamble.**

The complexity class [**AM**](http://en.wikipedia.org/wiki/Arthur%E2%80%93Merlin_protocol#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**?

**Tags:** cc.complexity-theory, interactive-proofs, unique-solution

> **Comments:**
> **username_1**: 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….  
> **username_2**: 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.  
> **username_1**: @Emil: I understand that if “high probability” is 1/poly, but is it possible to increase that probability to, say, a constant?  
> **username_2**: Fair enough, that’s actually a rather small probability. I don’t know how to make it a constant.  
> **username_1**: @Emil: I have just remembered a related paper by Kabanets and Watanabe ([see related question](http://cstheory.stackexchange.com/questions/7552/derandomizing-valiant-vazirani)).  
> **username_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.  
> **username_0**: @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?  
> **username_1**: 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).  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_3 on 2019-03-23. Score: 1

Koiran's paper [Hilbert's Nullstellensatz is in the Polynomial Hierarchy](https://www.sciencedirect.com/science/article/pii/S0885064X96900199) 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.


---

