Algebraic methods for interactive proof systems

A new algebraic technique for the construction of interactive proof systems is presented. Our technique is used to prove that every language in the polynomial-time hierarchy has an interactive proof system. This technique played a pivotal role in the recent proofs that IP = PSPACE [28] and that MIP...

Full description

Saved in:
Bibliographic Details
Published in:Journal of the ACM 1992-10, Vol.39 (4), p.859-868
Main Authors: LUND, C, FORTNOW, L, KARLOFF, H, NISAN, N
Format: Article
Language:English
Subjects:
Algebra
Applied sciences
Artificial intelligence
Computer science
control theory
systems
Construction
Exact sciences and technology
Hierarchies
Interactive
Problem solving, game playing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A new algebraic technique for the construction of interactive proof systems is presented. Our technique is used to prove that every language in the polynomial-time hierarchy has an interactive proof system. This technique played a pivotal role in the recent proofs that IP = PSPACE [28] and that MIP = NEXP [4].
ISSN:0004-5411
1557-735X
DOI:10.1145/146585.146605