FoCM 2014 conference

Workshop A6 - Real Number Complexity - Semi-plenary talk

December 12, 15:35 ~ 16:25 - Room C11

Probabilistically Checkable Proofs over the Reals

Klaus Meer

Brandenburg Technical University Cottbus - Senftenberg, Germany   -

One fruitful source of interesting problems in structural complexity theory over the reals since its introduction by Blum, Shub, and Smale in 1989 has been the investigation of major theorems known in classical (Turing) complexity within the real number framework. Prominent examples are the P versus NP question, decidability algorithms for problems in NP over the reals, and the theorems by Ladner and Toda, to mention a few only.

A cornerstone in Turing complexity theory is the PCP theorem shown in the early 1990's by Arora et al. It gives an alternative characterization of the complexity class NP via so-called probabilistically checkable proofs. Roughly speaking, it shows that a verification algorithm for instances of problems in NP can be designed such that a false verification proof can be detected with high probability by reading constantly many proof bits only. The theorem has shown huge impact on approximation problems as well.

It is thus natural to ask whether a similar characterization holds for the class NP$_{\Bbb{R}}$ of problems in NP over the reals. This boils down to the question whether there is a (randomized) procedure that verifies a solvability proof of a polynomial system over the reals by only inspecting a constant number of real components in the proof. Obviously, the natural NP$_{\Bbb{R}}$-verification proof that takes a zero and just plugs it into the system fails.

In the talk we shall report on techniques and results that we have been working on during the last couple of years in order to design real number PCPs. We explain the role of property testing and shall outline the proof of the corresponding PCP theorem both in the real and complex number BSS model. A focus will be on highlighting the differences (and non-differences) to the existing proofs of the classical PCP theorem.

Joint work with Martijn Baartse (Brandenburg Technical University Cottbus - Senftenberg, Germany).

View abstract PDF