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 study of tools as well as of books should have a place in the public schools. Tools, machinery, and the implements of the farm should be made familiar to every boy, and suitable industrial education should be furnished for every girl.”
—Rutherford Birchard Hayes (1822–1893)
“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)
“As in private life one differentiates between what a man thinks and says of himself and what he really is and does, so in historical struggles one must still more distinguish the language and the imaginary aspirations of parties from their real organism and their real interests, their conception of themselves from their reality.”
—Karl Marx (1818–1883)