Research output: Contribution to journal › Article › peer-review
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.
| Original language | English |
|---|---|
| Pages (from-to) | 330-345 |
| Number of pages | 16 |
| Journal | Computational Complexity |
| Volume | 8 |
| Issue number | 4 |
| DOIs | |
| State | Published - 1 Jan 1999 |
ID: 49986392