October 1992 | CARSTEN LUND, LANCE FORTNOW, AND HOWARD KARLOFF AND NOAM NISAN
This paper presents a new algebraic technique for constructing interactive proof systems, which is used to prove that every language in the polynomial-time hierarchy has an interactive proof system. This technique was pivotal in proving that IP = PSPACE and that MIP = NEXP. The main result is an interactive proof system for the permanent of 0-1 matrices, which implies that every language in the polynomial-time hierarchy has an interactive proof system. The technique involves reducing the problem of verifying the value of a low-degree polynomial at two points to verifying the value at one new point. The paper also discusses implications for program checking, verification, and self-correction. The result does not relativize, and it is the first to "go contrary" to a previously published oracle. The paper also provides a protocol for verifying the permanent of a 0-1 matrix, which is used to prove that every language in the polynomial-time hierarchy has an interactive proof system. The protocol involves a series of expand and shrink steps to reduce the matrix size until a 1x1 matrix is reached. The paper also discusses extensions of the protocol, including reducing the number of rounds and applications to program checking. The paper concludes with implications for the polynomial-time hierarchy and the relationship between interactive proof systems and program testing.This paper presents a new algebraic technique for constructing interactive proof systems, which is used to prove that every language in the polynomial-time hierarchy has an interactive proof system. This technique was pivotal in proving that IP = PSPACE and that MIP = NEXP. The main result is an interactive proof system for the permanent of 0-1 matrices, which implies that every language in the polynomial-time hierarchy has an interactive proof system. The technique involves reducing the problem of verifying the value of a low-degree polynomial at two points to verifying the value at one new point. The paper also discusses implications for program checking, verification, and self-correction. The result does not relativize, and it is the first to "go contrary" to a previously published oracle. The paper also provides a protocol for verifying the permanent of a 0-1 matrix, which is used to prove that every language in the polynomial-time hierarchy has an interactive proof system. The protocol involves a series of expand and shrink steps to reduce the matrix size until a 1x1 matrix is reached. The paper also discusses extensions of the protocol, including reducing the number of rounds and applications to program checking. The paper concludes with implications for the polynomial-time hierarchy and the relationship between interactive proof systems and program testing.