Public Coins Versus Private Coins
In the same conference where Babai defined his proof system for MA, Shafi Goldwasser, Silvio Micali and Charles Rackoff published a paper defining the interactive proof system IP. This has the same machines as the MA protocol, except that f(n) rounds are allowed for an input of size n. In each round, the verifier performs computation and passes a message to the prover, and the prover performs computation and passes information back to the verifier. At the end the verifier must make its decision. For example, in an IP protocol, the sequence would be VPVPVPV, where V is a verifier turn and P is a prover turn.
In Arthur–Merlin protocols, Babai defined a similar class AM which allowed f(n) rounds, but he put one extra condition on the machine: the verifier must show the prover all the random bits it uses in its computation. The result is that the verifier cannot "hide" anything from the prover, because the prover is powerful enough to simulate everything the verifier does if it knows what random bits it used. We call this a public coin protocol, because the random bits ("coin flips") are visible to both machines. The IP approach is called a private coin protocol by contrast.
The essential problem with public coins is that if the prover wishes to maliciously convince the verifier to accept a string which is not in the language, it seems like the verifier might be able to thwart its plans if it can hide its internal state from it. This was a primary motivation in defining the IP proof systems.
In 1986, Goldwasser and Sipser showed, perhaps surprisingly, that the verifier's ability to hide coin flips from the prover does it little good after all, in that an Arthur–Merlin public coin protocol with only two more rounds can recognize all the same languages. The result is that public-coin and private-coin protocols are roughly equivalent. In fact, as Babai shows in 1988, AM=AM for all constant k, so the IP have no advantage over AM.
To demonstrate the power of these classes, consider the graph isomorphism problem, the problem of determining whether it is possible to permute the vertices of one graph so that it is identical to another graph. This problem is in NP, since the proof certificate is the permutation which makes the graphs equal. It turns out that the complement of the graph isomorphism problem, a co-NP problem not known to be in NP, has an AM algorithm and the best way to see it is via a private coins algorithm.
Read more about this topic: Interactive Proof System
Famous quotes containing the words public, coins and/or private:
“Wags try to invent new stories to tell about the legislature, and end by telling the old one about the senator who explained his unaccustomed possession of a large roll of bills by saying that someone pushed it over the transom while he slept. The expression “It came over the transom,” to explain any unusual good fortune, is part of local folklore.”
—For the State of Montana, U.S. public relief program (1935-1943)
“A war undertaken without sufficient monies has but a wisp of force. Coins are the very sinews of battles.”
—François Rabelais (1494–1553)
“The private citizen, beset by partisan appeals for the loan of his Public Opinion, will soon see, perhaps, that these appeals are not a compliment to his intelligence, but an imposition on his good nature and an insult to his sense of evidence.”
—Walter Lippmann (1889–1974)