We 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))$.
We 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))$.
We 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))$.
