The NP-Completeness Column: An Ongoing Guide (Number 21: Interactive Proof Systems for Fun and Profit)
- Johnson D.
This column will be devoted to the concept of the "interactive proof system," together with its popular spin-off, the "zero-knowledge" proof. Recent STOC and FOCS conferences have seen an outpouring of papers on these topics, and it will be impossible for me to cover them all. I shall, however, try to sketch what appear today to be the major issues and results, as usual placing special emphasis on their relation to the theory of NP-completeness.