P vs NP over various structures

Johann Makowsky (Faculty of Computer Science, Technion – Israel Institute of Technology, Haifa, Israel) and Klaus Meer (BTU Cottbus-Senftenberg, Germany)

This fundamental course intends to present an introduction into topics relevant to computability and complexity theory over general structures with a particular emphasis on real and complex numbers. Computability over general structures was introduced relatively early, by E. Engeler in 1967 and H. Friedman in 1971. In these early attempts there is no discussion of non-determinism. In 1989, Blum, Shub, and Smale introduced a machine model for computations over arbitrary structures with a focus on the real and complex numbers. It is a uniform model relating previous approaches from algebraic complexity theory with classical questions about uniform complexity classes.

One of its main novelties is the introduction of non-determinisms in two versions: Binary non-determinisms with a bounded possibility of binary guesses, and general non-determinisms, with a possibly infinite possibility of guesses. As highlight of this new approach, an analogue of the P versus
NP question is obtained for both real and complex number complexity
theory. Though the concepts of computability, decidability and complexity are easily defined in the BSS model, many questions turn out to be of a very different flavour. Some problems can be solved similarly to the Turing model counterparts, whereas others either have very different solutions or different proofs. Moreover, they often lead to new interesting problems. The course will discuss such problems and new aspects that enter.

Course Materials