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.

Язык оригиналаанглийский
Страницы (с-по)330-345
Число страниц16
ЖурналComputational Complexity
Том8
Номер выпуска4
DOI
СостояниеОпубликовано - 1 янв 1999

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

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

ID: 49986392