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+.

Язык оригиналаанглийский
Название основной публикацииSTACS 98 - 15th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
Страницы499-510
Число страниц12
DOI
СостояниеОпубликовано - 1 дек 1998
Событие15th Annual Symposium on Theoretical Aspects of Computer Science, STACS 98 - Paris, Франция
Продолжительность: 25 фев 199827 фев 1998

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том1373 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция15th Annual Symposium on Theoretical Aspects of Computer Science, STACS 98
Страна/TерриторияФранция
ГородParis
Период25/02/9827/02/98

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 49986481