Refine
Document Type
- Doctoral thesis (1)
Has Fulltext
- yes (1)
Is part of the Bibliography
- no (1)
Year of publication
- 2015 (1)
Language
- English (1)
Keywords
- PCP (1) (remove)
Institute
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.