Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
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 |
ID: 49986392