DM/DMP82: Real number complexity and algorithms in semi-algebraic geometry (7.5 ECTS)

STADS: 1506042

Level
PhD course

Teaching period

Varying.

Teacher responsible
Email: meer@imada.sdu.dk

Timetable
There is no timetable available for the chosen semester.

Comment:
Kruset er et læsekursus.Valgfrit kursus.

Prerequisites:
None

Academic preconditions:
No special knowledge is required. DM19 must be known.

Course introduction
The course will give an introduction to real number complexity theory and algorithms important in semi-algebraic geometry. The basic model of computation used in computer science is the Turing machine. It is used for describing algorithms dealing with discrete structures (such as graphs, finite alphabets etc.). However, the last 15-20 years have seen a tremendous interest in alternative models of computation. Prominent examples are quantum computers, neural networks, DNA-computing or algebraic models. For many computational problems such an alternative model of computation seems to be a more natural framework for capturing certain aspects of the problem. In this course the central model of computation will be the real number model introduced by Blum, Shub and Smale in 1989. Here, real numbers are considered as basic computational entities. Problems treated with such a model typically have a so-called semi-algebraic structure. Examples are:
- problems in robotics (like robot motion planning or the piano movers problem, path-finding etc.)
- problems in computational geometry (such as finding connected components of sets, testing their emptyness, triangulations etc.)
- general problems that can be formalized via polynomial (in-) equality systems (like problems in kinematics, optimization theory, engineering).
The goal of this course is to give a precise introduction into the BSS model. We define and study real number complexity classes and basic algorithms related to these classes. Among the central algorithms studied in the course we will consider Tarski´s quantifier elimination algorithm (and variants) over the reals, one of the most important algorithms for problems involving polynomials.

Expected learning outcome


Subject overview
Alternative models of computation, real number algorithms, NP completeness over the reals, Tarski s algorithm.

Literature

• L. Blum, F. Cucker, M. Shub, S. Smale: Complexity and real computation.(Vi behandler kapitlerne 1-7, 16 og 21 (ca. 183 sider). Der vil bliv uddelt yderligere noter som K. Meer er i gang med at forberede. Disse vil fylde ca. 110 sider.) , Springer 1997, ISBN: 0-387-98281-7.

Syllabus
See syllabus.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:
Oral examination with an external examiner. Grades according to the 13-point scale. There will be homework assignments which students must get approved in order to take the exam.

Expected working hours
The teaching method is based on three phase model.

Forelæsninger (30 timer), eksaminatorier (30 timer).
Educational activities

Language
No recorded information about the language used in the course.

Remarks
1.) The course fits well together with the course on Computable Analysis taught by M. Ziegler in parallel. This course will deal with yet another model of computability over the real numbers. Thus, both courses together will shed light on the computational aspects of real number problems from different points of view.
2.) The course might be interesting for students of mathematics as well. In particular, those who followed the course MM85 will realize close relations to questions around Godel s incompleteness theorem. Tarski s algorithm actually shows that Godel s incompleteness theorem does not hold over structures like the real numbers.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.