Revision #2 Authors: Oded Goldreich, Johan Håstad

Accepted on: 16th April 1997 00:00

Downloads: 2001

Keywords:

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

Revision #1 Authors: Oded Goldreich, Johan Håstad

Accepted on: 11th April 1997 00:00

Downloads: 2173

Keywords:

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

TR96-018 Authors: Oded Goldreich, Johan Håstad

Publication: 24th February 1996 11:21

Downloads: 2188

Keywords:

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