Baartse, Martijn ;
Meer, Klaus
Real Interactive Proofs for VPSPACE
Abstract
We study interactive proofs in the framework of real number complexity as introduced by Blum, Shub, and Smale. The ultimate goal is to give a Shamir like characterization of the real counterpart IP_R of classical IP. Whereas classically Shamir's result implies IP = PSPACE = PAT = PAR, in our framework a major difficulty arises from the fact that in contrast to Turing complexity theory the real number classes PAR_R and PAT_R differ and space resources considered alone are not meaningful. It is not obvious to see whether IP_R is characterized by one of them  and if so by which.
In recent work the present authors established an upper bound IP_R is a subset of MA(Exists)R, where MA(Exists)R is a complexity class satisfying PAR_R is a strict subset of MA(Exists)R, which is a subset of PAT_R and conjectured to be different from PAT_R. The goal of the present paper is to complement this result and to prove interesting lower bounds for IP_R. More precisely, we design interactive real protocols for a large class of functions introduced by Koiran and Perifel and denoted by UniformVSPACE^0. As consequence, we show PAR_R is a subset of IP_R, which in particular implies coNP_R is a subset of IP_R, and P_R^{Res} is a subset of IP_R, where Res denotes certain multivariate Resultant polynomials.
Our proof techniques are guided by the question in how far Shamir's classical proof can be used as well in the real number setting. Towards this aim results by Koiran and Perifel on UniformVSPACE^0 are extremely helpful.
BibTeX  Entry
@InProceedings{baartse_et_al:LIPIcs:2016:6430,
author = {Martijn Baartse and Klaus Meer},
title = {{Real Interactive Proofs for VPSPACE}},
booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
pages = {14:114:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770163},
ISSN = {18688969},
year = {2016},
volume = {58},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6430},
URN = {urn:nbn:de:0030drops64300},
doi = {10.4230/LIPIcs.MFCS.2016.14},
annote = {Keywords: interactive proofs, real number computation, Shamir's theorem}
}
2016
Keywords: 

interactive proofs, real number computation, Shamir's theorem 
Seminar: 

41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Issue date: 

2016 
Date of publication: 

2016 