ECCC-Report TR96-018https://eccc.weizmann.ac.il/report/1996/018Comments and Revisions published for TR96-018en-usWed, 16 Apr 1997 00:00:00 +0300
Revision 2
| On the Complexity of Interactive Proof with Bounded Communication Revision of: TR96-018 |
Oded Goldreich,
Johan Hastad
https://eccc.weizmann.ac.il/report/1996/018#revision2We investigate the computational complexity of languages
which have interactive proof systems of bounded message complexity.
In particular, denoting the length of the input by $n$, we show that
(1) If $L$ has an interactive proof in which the total
communication is bounded by $c(n)$ bits
then $L$ can be recognized by a probabilitic machine
in time exponential in $O(c(n) + \log(n))$.
(2) If $L$ has an AM-proof in which the prover sends $c(n)$ bits
then $L$ can be recognized by a probabilitic machine
in time exponential in $O(c(n)\log(c(n)) + \log(n))$.
(3) If $L$ has an interactive proof in which the prover sends $c(n)$ bits
then $L$ can be recognized by a probabilitic machine with an NP-oracle
in time exponential in $O(c(n)\log(c(n)) + \log(n))$.
Wed, 16 Apr 1997 00:00:00 +0300https://eccc.weizmann.ac.il/report/1996/018#revision2
Revision 1
| On the Message Complexity of Interactive Proof Systems Revision of: TR96-018 |
Oded Goldreich,
Johan Hastad
https://eccc.weizmann.ac.il/report/1996/018#revision1We investigate the computational complexity of languages
which have interactive proof systems of bounded message complexity.
In particular, denoting the length of the input by $n$, we show that
(1) If $L$ has an interactive proof in which the total
communication is bounded by $c(n)$ bits
then $L$ can be recognized by a probabilitic machine
in time exponential in $O(c(n) + \log(n))$.
(2) If $L$ has an AM-proof in which the prover sends $c(n)$ bits
then $L$ can be recognized by a probabilitic machine
in time exponential in $O(c(n)\log(c(n)) + \log(n))$.
(3) If $L$ has an interactive proof in which the prover sends $c(n)$ bits
then $L$ can be recognized by a probabilitic machine with an NP-oracle
in time exponential in $O(c(n)\log(c(n)) + \log(n))$.
Fri, 11 Apr 1997 00:00:00 +0300https://eccc.weizmann.ac.il/report/1996/018#revision1
Paper TR96-018
| On the Message Complexity of Interactive Proof Systems |
Oded Goldreich,
Johan Hastad
https://eccc.weizmann.ac.il/report/1996/018We investigate the computational complexity of languages
which have interactive proof systems of bounded message complexity.
In particular, we show that
(1) If $L$ has an interactive proof in which the total
communication is bounded by $c(n)$ bits
then $L$ can be recognized a probabilitic machine
in time exponential in $O(c(n) + \log(n))$.
(2) If $L$ has an AM-proof in which the prover sends $c(n)$ bits
then $L$ can be recognized a probabilitic machine
in time exponential in $O(c(n)\log(c(n)) + \log(n))$.
(3) If $L$ has an interactive proof in which the prover sends $c(n)$ bits
then $L$ can be recognized a probabilitic machine with an NP-oracle
in time exponential in $O(c(n)\log(c(n)) + \log(n))$.
Sat, 24 Feb 1996 11:21:47 +0200https://eccc.weizmann.ac.il/report/1996/018