Advertisement
Published in:
2015 | OriginalPaper | Chapter
Some Results on Interactive Proofs for Real Computations
Authors : Martijn Baartse, Klaus Meer
Published in: Evolving Computability
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
We study interactive proofs in the framework of real number complexity theory as introduced by Blum, Shub, and Smale. Shamir’s famous result characterizes the class IP as PSPACE or, equivalently, as PAT and PAR in the Turing model. Since space resources alone are known not to make much sense in real number computations the question arises whether IP can be similarly characterized by one of the latter classes. Ivanov and de Rougemont [9] started this line of research showing that an analogue of Shamir’s result holds in the additive Blum-Shub-Smale model of computation when only Boolean messages can be exchanged. Here, we introduce interactive proofs in the full BSS model. As main result we prove an upper bound for the class \(\mathrm{IP}_{{\mathbb R}}\). It gives rise to the conjecture that a characterization of \(\mathrm{IP}_{{\mathbb R}}\) will not be given via one of the real complexity classes \(\mathrm{PAR}_{{\mathbb R}}\) or \(\mathrm{PAT}_{{\mathbb R}}\). We report on ongoing approaches to prove as well interesting lower bounds for \(\mathrm{IP}_{{\mathbb R}}\).