Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
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 фев 1998 → 27 фев 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/98 → 27/02/98 |
ID: 49986481