nach oben

Foundations of Computational Mathematics

Erschienen in:

01.06.2015

The PCP Theorem for NP Over the Reals

verfasst von: Martijn Baartse, Klaus Meer

Erschienen in: Foundations of Computational Mathematics | Ausgabe 3/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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 \(\mathrm{NP}_{{\mathbb {R}}}\) of the classical Turing model class NP can be characterized as \(\mathrm{NP}_{{\mathbb {R}}}= \mathrm{PCP}_{{\mathbb {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 \(\mathrm{NP}_{{\mathbb {C}}}\).

Vorheriger Artikel The Theory of the Interleaving Distance on Multidimensional Persistence Modules

Nächster Artikel Random Triangle Theory with Geometry and Applications

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

For a precise definition of the \(\mathrm{PCP}\) classes see the next section.

According to Definition 6 this implies that for each step in a random walk the probability that a loop is taken is at least \(\frac{1}{2}\).

These requirements are not included in the classical construction due to the underlying finite alphabets. It will become obvious below why it is needed over the reals.

The proof for \(\text{ NP }_{{\mathbb {C}}}\) is given in [5]. It seems that the verification proof used in [15], which basically consists of a test-set for certain linear functions, has to be enlarged; this does not change much the reasoning. The suitably modified arguments are given in [5].

If the reader does not want to dive into the construction of real long transparent proofs one can alternatively argue here as follows: The verifier computes its result in \(poly(s(t))\) many steps once the \(Q\) coordinates have been determined. Describe this deterministic computation once again as above in terms of a QPS\((1, poly(s(t)), \tilde{Q},1)\)-instance, where all polynomials involved in the new constraint are of degree at most \(2\) and depend on at most \(3\) variables. Here, \(\tilde{Q}\) depends polynomially on \(Q\) and \(s(t)\). Since we start from a fixed \(s\) and since \(t\) is constant, we obtain the desired statement, but with different constants for \(C\) and \(Q\).

These linear functions correspond to the Walsh–Hadamard code in the discrete framework.

Note a technical detail here: The verifier guarantees the function value table to be close to a linear function on \(\mathcal{X}_0\). It is easy to extend this verifier without using significantly more resources in such a way that this property also holds for subtables representing functions of a smaller arity. This is tacitly used above for coding the linear functions with coefficient vectors \(u^{(1)}\) and \(v^{(2)}\), respectively.

This viewpoint is taken because preprocessing, amplification, and dimension reduction are repeated several times.

S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.

S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, Proof verification and hardness of approximation problems, J. ACM 45 (3), (1998), 501–555. Extended abstract in Proc. of the 33rd Annual Symposium on Foundations of Computer Science, IEEE Computer Society, 1992, 14–23.

S. Arora and S. Safra, Probabilistic checking proofs: a new characterization of \(NP\), J. ACM 45 (1), (1998), 70–122. Extended abstract in Proc. of the 33rd Annual Symposium on the Foundations of Computer Science, IEEE Computer Society, 1992, 2–13.

M. Baartse and K. Meer, Testing low degree trigonometric polynomials. Extended abstract in Proc. 9th International Computer Science Symposium in Russia CSR 2014, Moscow (N.K. Vereshchagin, E.A. Hirsch, S.O. Kuznetsov, and J.E. Pin, eds.), Springer LNCS, 2014.

M. Baartse and K. Meer, Topics in real and complex number complexity theory, in Recent Advances in Real Complexity and Computation (J.L. Montaña and L.M. Pardo, eds.), Contemporary Mathematics, vol. 604, American Mathematical Society (2013), 1–53.

M. Baartse and K. Meer, The PCP Theorem for NP over the Reals. Extended abstract in Proc. 30th Symposium on Theoretical Aspects of Computer Science STACS 2013 (N. Portier and T. Wilke, eds.), Leibniz International Proceedings in Informatics (LIPIcs), vol. 20, Schloss Dagstuhl - Leibniz Zentrum für Informatik (2013), pp. 104–115, doi:10.4230/LIPIcs.STACS.2013.104.

L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and Real Computation, Springer, 1998.

L. Blum, M. Shub, and S. Smale, On a theory of computation and complexity over the real numbers, NP-completeness, recursive functions and universal machines, Bull. Amer. Math. Soc., vol. 21 (1989), 1–46.CrossRefMATHMathSciNet

F. Cucker and M. Matamala, On digital nondeterminism. Mathematical Systems Theory 29 (1996), 635–647.CrossRefMATHMathSciNet

10.

F. Cucker, M. Karpinski, P. Koiran, T. Lickteig, and K. Werther, On Real Turing Machines that Toss Coins, in Proceedings 27th Annual ACM Symposium on the Theory of Computing STOC (1995), 335–342.

11.

I. Dinur, The PCP theorem by gap amplification. J. ACM vol. 54 (3), Article 12 (2012). doi:10.1145/1236457.1236459.

12.

K. Friedl, Z. Hátsági and A. Shen, Low-Degree Tests, in Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms SODA (D.D. Sleator, ed.), 1994, 57–64.

13.

O. Goldreich, Basic Facts about Expander Graphs, in Studies in Complexity and Cryptography (O. Goldreich, ed.), Springer Lecture Notes in Computer Science 6650, 2011, 451–464.

14.

K. Meer, Almost Transparent Short Proofs for NP\(_{\mathbb{R}}\), Extended abstract in Proc. 18th International Symposium on Fundamentals of Computation Theory FCT 2011 (O. Owe, M. Steffen, and J.A. Telle, eds.), Lecture Notes in Computer Science 6914, 2011, 41–52.

15.

K. Meer, Transparent long proofs: a first PCP theorem for NP\(_{\mathbb{R}}\), , Vol. 5, Nr. 3 (2005), 231–255.CrossRefMATHMathSciNet

16.

O. Reingold, S. Vadhan, and A. Wigderson, Entropy waves, the zig-zag graph product, and new constant degree expanders, Annals of Mathematics, vol. 155 (2002), 157–187.CrossRefMATHMathSciNet

Titel: The PCP Theorem for NP Over the Reals
verfasst von: Martijn Baartse
Klaus Meer
Publikationsdatum: 01.06.2015
Verlag: Springer US
Erschienen in: Foundations of Computational Mathematics / Ausgabe 3/2015
Print ISSN: 1615-3375
Elektronische ISSN: 1615-3383
DOI: https://doi.org/10.1007/s10208-014-9188-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 3/2015

Random Triangle Theory with Geometry and Applications

Sliding Windows and Persistence: An Application of Topological Methods to Signal Analysis

Typical Real Ranks of Binary Forms

A PDE Approach to Fractional Diffusion in General Domains: A Priori Error Analysis

Adaptive Restart for Accelerated Gradient Schemes

The Theory of the Interleaving Distance on Multidimensional Persistence Modules

Premium Partner