7
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ Google does not readily spit out anything obviously relevent on "Arthur theorem prover". Can you please give a reference? $\endgroup$
    – Raphael
    Commented Jan 26, 2011 at 19:17
  • $\begingroup$ 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$". $\endgroup$
    – Raphael
    Commented Jan 26, 2011 at 19:19
  • 5
    $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Commented Jan 26, 2011 at 20:08
  • $\begingroup$ @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. $\endgroup$
    – echoone
    Commented Jan 27, 2011 at 21:35
  • 1
    $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Commented Jan 27, 2011 at 22:02

3 Answers 3

Reset to default
13
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – echoone
    Commented Jan 28, 2011 at 14:44
  • $\begingroup$ @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. $\endgroup$
    – Tsuyoshi Ito
    Commented Jan 30, 2011 at 23:17
9
$\begingroup$

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).

Improve this answer
$\endgroup$
4
  • $\begingroup$ Your example is that of a problem in the class AM, correct? $\endgroup$
    – echoone
    Commented Jan 27, 2011 at 21:37
  • $\begingroup$ @echoone: Correct. $\endgroup$
    – Peter Shor
    Commented Jan 27, 2011 at 22:41
  • 2
    $\begingroup$ I hesitate to use the names “Arthur” and “Merlin” when talking about private-coin interactive proof systems. $\endgroup$
    – Tsuyoshi Ito
    Commented Jan 28, 2011 at 0:05
  • 1
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Commented Jan 28, 2011 at 3:47
6
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I think that you are describing a probabilistically checkable proof (PCP) system instead of an interactive proof system. $\endgroup$
    – Tsuyoshi Ito
    Commented Jan 27, 2011 at 1:01
  • 2
    $\begingroup$ It's not clear which one of these concepts the OP is asking about. $\endgroup$
    – Peter Shor
    Commented Jan 27, 2011 at 2:55
  • $\begingroup$ Yeah, I thought the OP was asking about that, sorry if this is not the case. $\endgroup$
    – Abel Molina
    Commented Jan 27, 2011 at 3:20

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.