DOI

We introduce the class IPℛ+ (resp. IPℛ×) as the class of languages that admit an interactive protocol on the reals when the verifier is a BSS-machine with addition (resp. addition and multiplication). Let BIPℛ+ (resp. BIPℛ×) be its restriction when only boolean messages can be exchanged between the prover and the verifier. We prove that the classes BIPℛ+ and PARℛ+, the class of languages accepted in parallel polynomial time, coincide. In the case of multiplicative machines, we show that BIPℛ× ⊆ PARℛ×. We also separate BIP from IP in both models by exhibiting a language L which is not in PARℛ× but in IPℛ×. As a consequence we show that additive quantifier elimination cannot be solved in PARℛ× and that all boolean languages admit an interactive proof with addition and a real constant.

Original languageEnglish
Pages (from-to)330-345
Number of pages16
JournalComputational Complexity
Volume8
Issue number4
DOIs
StatePublished - 1 Jan 1999

    Scopus subject areas

  • Theoretical Computer Science
  • Mathematics(all)
  • Computational Theory and Mathematics
  • Computational Mathematics

    Research areas

  • Interactive proof, Real computation

ID: 49986392