NeuroCOLT

Neural Networks and Computational Learning Theory

About NeuroCOLT

Papers Archive

Books

info@neurocolt.org

NeuroCOLT Technical Report NC-TR-95-014

Grundlagen der reellen Komplexitätstheorie

Klaus Meer
RWTH Aachen

Abstract (in English - text is in German)
Complexity theory deals with the question of classifying mathematical problems according to the difficulty they provide for algorithmic solutions. This is generally related to

• finding efficient solution-algorithms,

• analyzing structural properties which make problems difficult to solve and

• comparing problems.

Contrary to the situation in classical complexity theory the real approach is interested in studying problems defined on continuous structures. Starting point for the present lecture notes will be the model of a real Turing-machine as it was introduced 1989 by Blum, Shub, and Smale. We will begin with a formal definition of notions like computability, decidability and efficiency. This gives rise to consider the complexity classes $P_{\R}$ and $NP_{\R}$. After analyzing basic properties (reducibility, $NP_{\R}-$completeness,existence of complete problems) we'll care about decidability of problems in class $NP_{\R}$. To this aim results on quantifier elimination and on the structure of semialgebraic sets are investigated. Finally, methods for proving lower bounds are presented. For this purpose we show a real version of Hilbert's Nullstellensatz.

Table of contents

0. Introduction
1. The computational model of Blum, Shub, and Smale
2. Complexity theory for the BSS-model
3. Existential theory over the reals
4. Lower bounds

Download Compressed Postscript