DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2016.14

Real Interactive Proofs for VPSPACE

Authors: Martijn Baartse and Klaus Meer

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

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.

Cite as

Martijn Baartse and Klaus Meer. Real Interactive Proofs for VPSPACE. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 14:1-14:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{baartse_et_al:LIPIcs.MFCS.2016.14,
  author =	{Baartse, Martijn and Meer, Klaus},
  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 =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.14},
  URN =		{urn:nbn:de:0030-drops-64300},
  doi =		{10.4230/LIPIcs.MFCS.2016.14},
  annote =	{Keywords: interactive proofs, real number computation, Shamir's theorem}
}

Document

DOI: 10.4230/LIPIcs.STACS.2013.104

The PCP theorem for NP over the reals

Authors: Martijn Baartse and Klaus Meer

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract

In this paper we show that the PCP theorem holds as well in the real number computational model introduced by Blum, Shub, and Smale. More precisely, the real number counterpart NP_R of the classical Turing model class NP can be characterized as NP_R = PCP_R(O(log n), O(1)). Our proof structurally follows the one by Dinur for classical NP. However, a lot of minor and major changes are necessary due to the real numbers as underlying computational structure. The analogue result holds for the complex numbers and NP_C.

Cite as

Martijn Baartse and Klaus Meer. The PCP theorem for NP over the reals. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 104-115, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{baartse_et_al:LIPIcs.STACS.2013.104,
  author =	{Baartse, Martijn and Meer, Klaus},
  title =	{{The PCP theorem for NP over the reals}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{104--115},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.104},
  URN =		{urn:nbn:de:0030-drops-39262},
  doi =		{10.4230/LIPIcs.STACS.2013.104},
  annote =	{Keywords: PCP, real number computation, systems of polynomials}
}

Search Results

Documents authored by Baartse, Martijn

Real Interactive Proofs for VPSPACE

Abstract

Cite as

The PCP theorem for NP over the reals

Abstract

Cite as

Thanks for your feedback!

Could not send message