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:
“They had their fortunes to make, everything to gain and nothing to lose. They were schooled in and anxious for debates; forcible in argument; reckless and brilliant. For them it was but a short and natural step from swaying juries in courtroom battles over the ownership of land to swaying constituents in contests for office. For the lawyer, oratory was the escalator that could lift a political candidate to higher ground.”
—Federal Writers’ Project Of The Wor, U.S. public relief program (1935-1943)
“No Time, spoke the clocks, no God, rang the bells,
I drew the white sheet over the islands
And the coins on my eyelids sang like shells.”
—Dylan Thomas (1914–1953)
“A strange age of the world this, when empires, kingdoms, and republics come a-begging to a private man’s door, and utter their complaints at his elbow! I cannot take up a newspaper but I find that some wretched government or other, hard pushed and on its last legs, is interceding with me, the reader, to vote for it.”
—Henry David Thoreau (1817–1862)