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:
“The first man to discover Chinook salmon in the Columbia, caught 264 in a day and carried them across the river by walking on the backs of other fish. His greatest feat, however, was learning the Chinook jargon in 15 minutes from listening to salmon talk.”
—State of Oregon, 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)
“The decision to have a child is both a private and a public decision, for children are our collective future.”
—Sylvia Ann Hewitt (20th century)