Aim and scope.
This special session will cover various topics:
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
models of computation can help us to understand more about the
complexity of problems and the difficulty to solve the
classical P-NP problem.
- 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
- geometric computation, algorithmic algebraic geometry.
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.
(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. firstname.lastname@example.org