TY - THES A1 - Baartse, Willem Martijn T1 - The PCP theorem in real number complexity theory T1 - Das PCP-Theorem in der reellen Komplexitätstheorie N2 - In this thesis we consider probabilistically checkable proofs (PCPs) in the model of computation working with real and complex numbers as introduced by Blum, Shub and Smale (the BSS model). Starting point of this thesis is the so-called PCP theorem, a major result in complexity theory. Roughly speaking this theorem says that one can check the correctness of certain proofs of mathematical statements with high probability by only looking at small parts of the proof. PCPs have a natural formulation in the BSS model as well. Considering the importance of the PCP theorem it seems natural to ask whether a similar theorem holds in this model also. The PCP theorem in the Turing model has two qualitatively very different proofs. The original proof by Arora et al. uses mostly algebraic techniques. Later another, combinatorial proof was discovered by Dinur. In this thesis we give two corresponding proofs in the BSS model. Thereby we establish the PCP theorem in the framework of the real numbers as well as in the framework of the complex numbers. The main difficulties occur due to the fact that the structures R and C over which we work are uncountably infinite. For both classical proof techniques partially really new ideas are necessary to apply their structure to the new computational model. Apart from the importance of the PCP theorem it helps to better understand the similarities and differences between both models of computation. We hope that the new ideas we develop may be useful in other contexts as well. N2 - In dieser Arbeit betrachten wir probabilistisch prüfbare Beweise (Englisch: probabilistically checkable proofs PCPs) in einem Rechenmodell, das mit reellen und komplexen Zahlen arbeitet und 1989 durch Blum, Shub und Smale eingeführt wurde, dem BSS-Modell. Ausgangspunkt der Arbeit ist das sogenannte PCP-Theorem, eines der wichtigsten Resultate in der Komplexitätstheorie der letzten Jahrzehnte. Sehr grob gesprochen besagt es, dass man die Korrektheit von Beweisen mathematischer Aussagen mit hoher Wahrscheinlichkeit überprüfen kann, indem man nur sehr wenige Teile des Beweises untersucht. PCPs können auf natürliche Weise auch im BSS-Modell formuliert werden. Im Hinblick auf die Wichtigkeit des PCP-Satzes ist es daher naheliegend zu fragen, ob ein vergleichbares Ergebnis auch in diesem Modell gilt. Das klassische Theorem im Turingmodell hat zwei qualitativ sehr unterschiedliche Beweise. Der ursprüngliche Beweis von Arora et al. benutzt vorwiegend algebraische Techniken. Ein später gegebener Beweis von Dinur basiert im Wesentlichen auf kombinatorischen Methoden. In der vorliegenden Arbeit präsentieren wir zwei entsprechende Beweise im BSS-Modell. Der PCP-Satz wird dabei sowohl im reellen als auch im komplexen Rahmen bewiesen. Die wesentlichen neuen Schwierigkeiten bei beiden Beweisen resultieren aus der Überabzählbarkeit der zugrundeliegenden Strukturen R und C. Für beide klassische Beweismethoden erfordert dies zum Teil wesentlich neue Ideen, um ihre Struktur auf das neue Rechenmodell zu übertragen. Neben der Bedeutung des PCP-Satzes an sich hilft dies, die Ähnlichkeiten und Unterschiede zwischen beiden Rechenmodellen besser zu verstehen. Es ist zu hoffen, dass die neuen Ideen, die wir hier entwickeln, auch in anderen Kontexten nützlich sind. KW - PCP KW - BSS Model KW - Low-degree test KW - BSS-Modell KW - Niedriger-Grad Test KW - Komplexitätstheorie KW - Berechnungskomplexität Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-36244 ER -