Special Session

Logical Approaches to Barriers in Computing and Complexity

Workshop    Greifswald     17 - 20 February 2010
Aim and scope. This special session will cover various topics:
  • Turing machines over arbitrary structures, the BSS model, algebraic decision circuits, and other new models over algebraic structures,
  • definability, quantifiers and elimination,
  • computability and complexity over real-valued data, several cost measures,
  • geometric computation, algorithmic algebraic geometry.
The aim is to gain better insight into decidability and complexity of problems. There are several techniques which allow to investigate the complexity of decision problems over algebraic structures. Some of these techniques are based on the laws of logic only. For instance, by use of diagonalisation techniques one can prove the undecidability of the Halting Problem for any model of computation over any structure. For other proofs one needs only few additional axioms. On the assumption that an arbitrary structure of finite signature includes the identity relation, universal satisfiability problems can be introduced. Addition of further axioms yields restricted classes of structures underlying special models of computation, e.g. the BSS model over an ordered ring and other algebraic models used in Computational Geometry. Specifically, models over real numbers are often used in order to make first estimations of the complexity of algorithms. At first sight, some of the resulting relationships seem to be in contrast to the Turing-Church thesis. However, the investgation of common properties and differences of the algebraic models of computation can help us to understand more about the complexity of problems and the difficulty to solve the classical P-NP problem.
Keynote Speaker. Bruno Poizat (Villeurbanne, France): Transformations and Complexity.
Invited Speakers (all confirmed).
      Olivier Bournez (Palaiseau, France): Characterizing algebraically computability and complexity classes over the reals in recursive analysis.
      Klaus Meer (Cottbus, Germany): Diagonal sets for real number complexity classes.
      Monika Seisenberger (Swansea, Wales): Efficient synthesis of exact real number algorithms.
      Klaus Weihrauch (Hagen, Germany): Computational Complexity in Analysis.
      Joris van der Hoeven (Orsay, France): Ball arithmetic.
      Thierry Zell (Hickory, NC, USA) and Saugata Basu: Polynomial hierarchy, Betti numbers and a  real analogue of Toda's theorem.
      Martin Ziegler (Freiburg, Germany) and Katrin Tent (Münster, Germany): Computable Functions of Reals.
Organisers of the Special Session. Christine Gaßner (Greifswald, Germany), Martin Ziegler (Darmstadt, Germany).
More Information. gassnerc@uni-greifswald.de