Regular WS 98/99 (1012.98-18.2.99)

December 10, 1998

• Computation over discrete structures (Natural numbers, strings) vs. Computation over the reals.
• Example of geometrical constructions with ruler and compass. The work of Abel and Galois allows us to prove non-constructubility of the double cube and (using that the number pi is irrational) of doubling the circle.
• Matrix multiplication as an example of computability over the Reals (or any field)
• Organisational matters

December 17, 1998

Speaker: J.A. Makowsky

• Outline of topics and tasks.

• Definition of BSS Programs.
• Definition of Problems over the Reals (Complex numbers).
• Decidability and Halting sets. Semi-decidability, semi-computability.
• If a problem S is decidable then S is the Halting Set for some BSS Program (Machine) M. Converse false.
• Mandelbrot set Mand(R) over the reals is decidable.
• Mandelbrot set Mand(C) over the complex numbers (viewed as pairs of reals). The complement of Mand(C) is semi-decidable.
• We shall see later that Mand(C) is not decidable.

December 24, 1998

Speaker: J.A. Makowsky

• Remarks on didactic goals . In particular: We have to build a rpertoire of examples to sharpen our intuition.

• Julia sets J(t) of a polynomial t=t(x) (in one variable) over the reals.
• The complement of Julia set J(t) is semi-decidable.
• We shall see later that J(t) is not decidable for t(x)=x^2+4.
• Knapsack problem for fixed number of objects.
• Knapsack problem for variable number n of objects.
• Knapsack is decidable in exponential time.
• Define polynomial and exponential time over the Reals.

December 31, 1998

Speaker: J.A. Makowsky

• Reals and variations (sin, exp)
• Integers and variations (addition only, addition and squarin)
• First order logic for these structures (repetition): Terms, atomic formulas, boolean combination of atomuc formulas (=quantifier free formulas).
• Algebraic sets: Definable by finite sets of equations between terms (no order relation used).
• Proposition: An set $U \subseteq R$ is algebraic iff it is finite.
  This is not true for $U \subseteq R^n$.
  It is also not true for $U \subseteq R$ if we allow the function sin.
• Semi-algebraic sets: Definable by finite sets of quantifier free formulas (including order relation).
• Proposition: Every semi-algebraic set $U \subseteq R^n$ is BSS-decidable.
  Proof given in great detail.
• Homework: Show that the set of primes over the intgers Z is BSS-decidable. Show that the function f_prime(n)= 0 for n <0 and f_prime(n) = p_n, the n^th prime, is BSS-computable over the integers.
  Show that every formula over F_+, F_x is equivalent to a formula over F_+ and F_sq (using quantifiers). Can you do the same without quantifiers?

January 7(a), 1998

January 7(b), 1998

January 14, 1998

January 21(a), 1998

January 21(b), 1998

January 28, 1998

February 4, 1998

Strike period

22.10.98

29.10.98

Survey and introduction of the seminar topics.

• Algebraic complexity, some history and concetpt of algebraic computation.
• Classical computability theory: Turing Machines, recursively defined functions and Register Mchines
• Register Machines over arbitrary First order Structures.
• Informal definition of BSS-model over a structure A.
• Some sample theorems to be proven in the sequel.

5.11.98

Formal definition of BSS-model of computation.
Examples:Finding the middle coordinate of a vector, scalar product of two vectors, matrix multiplication, problems on weighted graphs.
Noting the difference between the real and complex numbers.
The complexity classes P and NP over the real and complex numbers.

12.11.98

Examples of problems in NP over the real and complex numbers. NP-completenss over the real and complex numbers.