License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2016.14
URN: urn:nbn:de:0030-drops-64300
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6430/
Go to the corresponding LIPIcs Volume Portal

Baartse, Martijn ; Meer, Klaus

Real Interactive Proofs for VPSPACE

pdf-format:
LIPIcs-MFCS-2016-14.pdf (0.4 MB)

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 co-NP_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:1--14:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6430},
  URN =		{urn:nbn:de:0030-drops-64300},
  doi =		{10.4230/LIPIcs.MFCS.2016.14},
  annote =	{Keywords: interactive proofs, real number computation, Shamir's theorem}
}

Keywords: interactive proofs, real number computation, Shamir's theorem
Collection: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Issue Date: 2016
Date of publication: 19.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI