<p>Your interpretation isn't using randomness in the right way in an MA protocol.</p>

<p>Every MA problem can be reduced to a polynomial-size circuit of AND-OR-NOT gates, with some input variables designated for Merlin and the rest designated for Arthur. First Merlin tells Arthur the TRUE-FALSE values of Merlin's variables. Then Arthur flips coins to choose the TRUE-FALSE values for Arthur's variables. That's all the randomness Arthur needs so he can now throw his coin away.</p>

<p>Now we have a logical circuit with no free variables. Arthur deterministically verifies that the circuit outputs true. </p>

CC BY-SA 2.5
2011-01-28T14:44:35.830Z
Would you provide me with a reference where this reduction is shown? It seems that if the circuit is not trivial (in the sense that there are only a couple of satisfying assignments), the output will be FALSE most of the time. But what does this mean? It is not clear to me what the output is supposed to represent in regards to the problem.
echoone
CC BY-SA 2.5
2011-01-30T23:17:09.347Z
@echoone: “It seems that if the circuit is not trivial (in the sense that there are only a couple of satisfying assignments), the output will be FALSE most of the time.”  Why do you consider a Boolean circuit with many satisfying assignments as “trivial”?  That does not make any sense to me.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-28T12:27:15.893Z
2011-01-28T12:27:15.893Z
Lance Fortnow
<p>I don't know whether you want to know about probabilistically checkable proofs or interactive proof systems. These two things are different. In interactive proof systems, there are two players, Arthur (the verifier) and Merlin (the prover), and they may perform several rounds of communication. For a probabilistically checkable proof the prover writes down a long proof, but the verifier only needs to check a few bits of it to be fairly sure the proof is correct.</p>

<p>The easiest interactive proof system to understand is the one showing that two graphs are not isomorphic. There are probably a number of better explanations on the web, but here's the short version. The verifier has two graphs $G_1$ and $G_2$, and the prover wants to show that they are not isomorphic. What the verifier can do is pick one of two graphs at random, and permute its vertices randomly. If the prover can reliably tell the verifier which of $G_1$ or $G_2$ the verifier chose, then the graphs are not isomorphic (or the prover was very, very lucky).</p>

CC BY-SA 2.5
2011-01-27T21:37:06.907Z
Your example is that of a problem in the class AM, correct?
echoone
CC BY-SA 2.5
2011-01-27T22:41:49.383Z
@echoone: Correct.
Peter Shor 
CC BY-SA 2.5
2011-01-28T00:05:25.987Z
I hesitate to use the names “Arthur” and “Merlin” when talking about private-coin interactive proof systems.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-28T03:47:23.620Z
You may hesitate; but I, having (until you reminded me) completely forgotten about the computational history of Arthur and Merlin, use these names with no hesitation whatsoever.
Peter Shor 
CC BY-SA 2.5
2011-01-27T02:48:06.637Z
2011-01-28T03:49:23.757Z
2011-01-28T03:49:23.757Z
Peter Shor 
<p>This should maybe be a comment, but it is too long:</p>

<p>An example that might help you to understand what is happening is the following situation:</p>

<p>Arthur has a SAT problem for which $s \in L$ is represented by a very large number of clauses with a very large number of variables. He might not be able to write down the whole list of clauses efficiently, but given an index, he can generate the corresponding clause efficiently, as well as check whether it is satisfied given an assignment of values to the variables in it. He also has a gap condition, that is, either it is possible to satisfy all clauses, or at most a constant fraction of them. </p>

<p>Then, a proof could be a string representing an assignment of values to the variables in Arthur's system. To verify probabilistically whether $s \in L$, Arthur selects a random clause, queries the positions in the string corresponding to the variables that appear in it, and checks whether the clause is satisfied. If it is satisfied he accepts, and otherwise he rejects.</p>

CC BY-SA 2.5
2011-01-27T01:01:43.460Z
I think that you are describing a probabilistically checkable proof (PCP) system instead of an interactive proof system.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-27T02:55:00.017Z
It's not clear which one of these concepts the OP is asking about.
Peter Shor 
CC BY-SA 2.5
2011-01-27T03:20:36.173Z
Yeah, I thought the OP was asking about that, sorry if this is not the case.
Abel Molina
CC BY-SA 2.5
2011-01-27T00:33:39.137Z
2011-01-27T00:33:39.137Z
Abel Molina
<p>I'm having a hard time understanding the way Arthur verifies proofs probabilistically with coin tosses in an intuitive manner.</p>

<p>Suppose Arthur is a logician equipped with paper, a pencil and an unbiased coin. Someone hands Arthur a proof that some string s is in some language L. How exactly does Arthur probabilistically check the proof? My interpretation is that he does the following: </p>

<p>Arthur tosses the coin. If it lands showing heads, he accepts the first statement without checking it. If it lands tails, he checks it. If, upon checking, he determines that the first statement is false, he rejects the proof. Otherwise, if he determines that the first statement is true, he continues this process with the next statement of the proof. If Arthur never rejects the proof during this process, then he accepts the proof if one of the statements is a concluding statement of the form "..., hence s is in L" and he rejects the proof otherwise.</p>

<p>Is this a correct interpretation?</p>

<p>Edit: I am not talking about probabilistically checkable proofs. The question above came about from thinking about the class MA. </p>

CC BY-SA 2.5
2011-01-26T19:17:27.857Z
Google does not readily spit out anything obviously relevent on "Arthur theorem prover". Can you please give a reference?
Raphael
CC BY-SA 2.5
2011-01-26T19:19:09.850Z
I can imagine a "prover" trying to guess counter examples. After a sufficient number of repetitions without finding a counter example, a statement along the lines of "this step can not be rejected as false with significance $p$".
Raphael
CC BY-SA 2.5
2011-01-26T20:08:10.067Z
No.  You have assumed that Merlin can write down the whole proof of the fact s∈L and pass it to Arthur, but that is possible only if the whole proof can be written as a string whose length is polynomially bounded in |s|.  If the whole proof is polynomial length, then Arthur can read the whole proof and does not have to skip part of it.  Things become interesting when we do not know whether there exists a polynomial-length certificate for the fact s∈L.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-27T21:35:50.840Z
@Tsuyoshi: Yes, I have assummed that Merlin can write down the whole proof. To keep things simple, I do not care about the length of the proof, as long as it is finite.
echoone
CC BY-SA 2.5
2011-01-27T22:02:31.867Z
My point is that if Merlin can send the whole proof to Arthur, then there is no point for Arthur to skip part of it.  If the length of the proof is not polynomially bounded, Merlin cannot send the whole proof to Arthur; interaction becomes essential in this case.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-27T22:06:49.537Z
Now I see the addendum to the question that you are looking for an explanation of MA.  Note that MA is a very special case of an Arthur-Merlin proof system, which is in turn a special case of an interactive proof system.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-15T06:00:28.923Z
I have realized that my problem is that my view of interactive proof systems wrong. I kept thinking of Merlin as a prover and Arthur as a verifier since this is what one reads in the literature. I have realized that it makes more sense to think of Arthur as a skeptic and Merlin as a sly know-it-all, although I should really just stick with the standard Turing machine definitions and not bother with these interpretations.
echoone
<cc.complexity-theory><big-picture><interactive-proofs>
How are proofs verified probabilistically in interactive proof systems?
echoone
# How are proofs verified probabilistically in interactive proof systems?

(Asked by: username_0 on 2011-01-26)

I'm having a hard time understanding the way Arthur verifies proofs probabilistically with coin tosses in an intuitive manner.

Suppose Arthur is a logician equipped with paper, a pencil and an unbiased coin. Someone hands Arthur a proof that some string s is in some language L. How exactly does Arthur probabilistically check the proof? My interpretation is that he does the following:

Arthur tosses the coin. If it lands showing heads, he accepts the first statement without checking it. If it lands tails, he checks it. If, upon checking, he determines that the first statement is false, he rejects the proof. Otherwise, if he determines that the first statement is true, he continues this process with the next statement of the proof. If Arthur never rejects the proof during this process, then he accepts the proof if one of the statements is a concluding statement of the form "..., hence s is in L" and he rejects the proof otherwise.

Is this a correct interpretation?

Edit: I am not talking about probabilistically checkable proofs. The question above came about from thinking about the class MA.

**Tags:** cc.complexity-theory, big-picture, interactive-proofs

> **Comments:**
> **username_1**: Google does not readily spit out anything obviously relevent on "Arthur theorem prover". Can you please give a reference?  
> **username_1**: I can imagine a "prover" trying to guess counter examples. After a sufficient number of repetitions without finding a counter example, a statement along the lines of "this step can not be rejected as false with significance $p$".  
> **username_2**: No.  You have assumed that Merlin can write down the whole proof of the fact s∈L and pass it to Arthur, but that is possible only if the whole proof can be written as a string whose length is polynomially bounded in |s|.  If the whole proof is polynomial length, then Arthur can read the whole proof and does not have to skip part of it.  Things become interesting when we do not know whether there exists a polynomial-length certificate for the fact s∈L.  
> **username_0**: @Tsuyoshi: Yes, I have assummed that Merlin can write down the whole proof. To keep things simple, I do not care about the length of the proof, as long as it is finite.  
> **username_2**: My point is that if Merlin can send the whole proof to Arthur, then there is no point for Arthur to skip part of it.  If the length of the proof is not polynomially bounded, Merlin cannot send the whole proof to Arthur; interaction becomes essential in this case.  
> **username_2**: Now I see the addendum to the question that you are looking for an explanation of MA.  Note that MA is a very special case of an Arthur-Merlin proof system, which is in turn a special case of an interactive proof system.  
> **username_0**: I have realized that my problem is that my view of interactive proof systems wrong. I kept thinking of Merlin as a prover and Arthur as a verifier since this is what one reads in the literature. I have realized that it makes more sense to think of Arthur as a skeptic and Merlin as a sly know-it-all, although I should really just stick with the standard Turing machine definitions and not bother with these interpretations.  

---

## 3 answers

### Answer by username_3 on 2011-01-28. Score: 13

Your interpretation isn't using randomness in the right way in an MA protocol.

Every MA problem can be reduced to a polynomial-size circuit of AND-OR-NOT gates, with some input variables designated for Merlin and the rest designated for Arthur. First Merlin tells Arthur the TRUE-FALSE values of Merlin's variables. Then Arthur flips coins to choose the TRUE-FALSE values for Arthur's variables. That's all the randomness Arthur needs so he can now throw his coin away.

Now we have a logical circuit with no free variables. Arthur deterministically verifies that the circuit outputs true.

> **Comments:**
> **username_0**: Would you provide me with a reference where this reduction is shown? It seems that if the circuit is not trivial (in the sense that there are only a couple of satisfying assignments), the output will be FALSE most of the time. But what does this mean? It is not clear to me what the output is supposed to represent in regards to the problem.  
> **username_2**: @username_0: “It seems that if the circuit is not trivial (in the sense that there are only a couple of satisfying assignments), the output will be FALSE most of the time.”  Why do you consider a Boolean circuit with many satisfying assignments as “trivial”?  That does not make any sense to me.  

---

### Answer by username_4 on 2011-01-27. Score: 9

I don't know whether you want to know about probabilistically checkable proofs or interactive proof systems. These two things are different. In interactive proof systems, there are two players, Arthur (the verifier) and Merlin (the prover), and they may perform several rounds of communication. For a probabilistically checkable proof the prover writes down a long proof, but the verifier only needs to check a few bits of it to be fairly sure the proof is correct.

The easiest interactive proof system to understand is the one showing that two graphs are not isomorphic. There are probably a number of better explanations on the web, but here's the short version. The verifier has two graphs $G\_1$ and $G\_2$, and the prover wants to show that they are not isomorphic. What the verifier can do is pick one of two graphs at random, and permute its vertices randomly. If the prover can reliably tell the verifier which of $G\_1$ or $G\_2$ the verifier chose, then the graphs are not isomorphic (or the prover was very, very lucky).

> **Comments:**
> **username_0**: Your example is that of a problem in the class AM, correct?  
> **username_4**: @username_0: Correct.  
> **username_2**: I hesitate to use the names “Arthur” and “Merlin” when talking about private-coin interactive proof systems.  
> **username_4**: You may hesitate; but I, having (until you reminded me) completely forgotten about the computational history of Arthur and Merlin, use these names with no hesitation whatsoever.  

---

### Answer by username_5 on 2011-01-27. Score: 6

This should maybe be a comment, but it is too long:

An example that might help you to understand what is happening is the following situation:

Arthur has a SAT problem for which $s \in L$ is represented by a very large number of clauses with a very large number of variables. He might not be able to write down the whole list of clauses efficiently, but given an index, he can generate the corresponding clause efficiently, as well as check whether it is satisfied given an assignment of values to the variables in it. He also has a gap condition, that is, either it is possible to satisfy all clauses, or at most a constant fraction of them.

Then, a proof could be a string representing an assignment of values to the variables in Arthur's system. To verify probabilistically whether $s \in L$, Arthur selects a random clause, queries the positions in the string corresponding to the variables that appear in it, and checks whether the clause is satisfied. If it is satisfied he accepts, and otherwise he rejects.

> **Comments:**
> **username_2**: I think that you are describing a probabilistically checkable proof (PCP) system instead of an interactive proof system.  
> **username_4**: It's not clear which one of these concepts the OP is asking about.  
> **username_5**: Yeah, I thought the OP was asking about that, sorry if this is not the case.  

---

