DOI

We introduce the classes IPR+ (resp. IPRx) 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 BIPR+ (resp. BIPRx) its restriction when only boolean messages can be exchanged between the prover and the verifier. We prove that the classes BIPR+ and PARR+, the class of languages accepted in parallel polynomial time coincide. In the case of multiplicative machines, we show that BIPRx ⊆ PARRx). We also separate BIP R from IPR in both models by exhibiting a language L which is not in PARRx but in IPR+. As a consequence we show that additive quantifier elimination can't be solved in PARRx and that all boolean languages are in IPR+.

Original languageEnglish
Title of host publicationSTACS 98 - 15th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
Pages499-510
Number of pages12
DOIs
StatePublished - 1 Dec 1998
Event15th Annual Symposium on Theoretical Aspects of Computer Science, STACS 98 - Paris, France
Duration: 25 Feb 199827 Feb 1998

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1373 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th Annual Symposium on Theoretical Aspects of Computer Science, STACS 98
Country/TerritoryFrance
CityParis
Period25/02/9827/02/98

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 49986481