Abstracts of Lectures and Tirgulim
Last updated: 15.5.02
13.3.2002
Tirgul: Cancelled
Lecture:
Models of computation over the reals.
Turing machines, Register machines,
Straightline programs, while programs,
Blum-Shub-Smale (BSS) Computing.
Slides available in the library
20.3.2002
Tirgul:
Some basic problems and their algorithmic solution.
Lecture:
Some Basic Problem and their formulation in BSS.
The classe P and NP in BSS
Slides available in the library
PESSACH
10.4.2002
Specification and implementation of
data structures in the language of sets.
The ordered pair as a simple example.
The natural numbers.
Axiomatic description of the reals as a complete ordered
field.
The axioms of real closed fields.
The construction of the complex numbers using the reals.
The axioms of algebraic closed fields.
Halting sets of algorithms in BSS.
YOM ATZMAUT
22.4.2002, Monday as Wednesday
Repetition of previous lecture
How to build the reals in the language of sets.
- The natural numbers, with inductive definition
of addition and multiplication (and order).
- The integers as quotient structure with
elements the equivalence classes of pairs of natural numbers
with the same difference.
- The rationals as quotient structure with
elements the equivalence classes of pairs of integers
with the same quotient.
- The reals as equivalence classes of
Cauchy sequences (or Dedekind cuts) of rationals.
Homework assignment:
- Prove properties of ordered pairs for various definitions.
- Check the "Implicit Function Theorem" from the
Calculus course.
24.4.2002
Tirgul:
Repetition of previous lecture.
Discussion of homework.
Lecture:
The Path decomposition theorem and its applications.
- (Non)-computability of the exponential function and its graph.
- NP-complete problems
01.5.2002
Tirgul:
Discussion of homework.
Why is f(x)= e^x not BSS computable?
Why is g(x,y)= 0 for y= e^x not BSS decidable?
Note that x=e is computable (using a machine constant e).
It is not computable without parameters.
Some comments on transcendental numbers,
and the implicit function theorem.
Some comments on the differentiability of e^x.
Lecture:
Topic: All NP_R problems are BSS-computable
(even in exponential time).
In BSS this is a deep theorem about real closed fields.
(In the Turing model this is trivial).
Tool: Quantifier elimination.
We made examples for the case
Exists x (ax^2 + bx +c =0) and
Exists x (ax^3 + bx^2 +cx +d =0)
We proved the cases:
- Easy: For formulas with equality only.
- Needs work: For formulas with equality and order.
General case (without complexity) will be discussed
in the next few lectures.
08.5.2002
Tirgul:
Discussion of homework.
Why does the ring
of the integers not have quantifier elimination?
Why does the ring
of rationals not have quantifier elimination?
Introduction of projects.
- Linear case of quantifier elimination (Fourier-Motzkin).
- Linear algorithms and problems (Eaves-Rothblum).
- Meta-finite models and BSS
- Sparsity conditions for polynomials.
Lecture:
Continuation of quantifier elimination.
The linear case.
15.5.2002
Tirgul:
Quantifier elimination over Z_2.
P_Ring = NP_Ring
iff Ring allows effective quantifier elimination.
Assume we have fast q.e.
Then resulting quantifier free formula is short
and gives P_Ring algorithm.
Converse needs precise statement about Path decomposition
of P-Time algorithms.
Homework: Fill in Gap in the proof.
Lecture:
Descartes Rule using sign changes.
Statement of the Fourier-Budan Theorem.
Material from
-
Henrici, Peter
Applied and computational complex analysis, vol. 1
c1974- Technion Library Number: 2005739
Chapter 6.2-6.3.
Sturm chains and Sturm's Theorem.
Material from Makowsky-Meer notes, pages 43ff.
A more sophisticated exposition is in
-
Marie-Francoise Roy,
Basic algorithms in real algebraic geometry and their complexity:
from Sturm's theorem to the existential theory of reals.
In: Lectures in real geometry, F. Broglia (ed.),
De Gruyter Expositions in Mathematics, vol. 23, 1996
p. 1-68.
22.5.2002
Tirgul:
Discussion of homework.
To be reconstructed
Lecture:
Polynomials in many variables of degree four.
Existence of roots is NP_R -complete.
Polynomials in many variables of degree three.
Existence of roots is in P_R
Proof not completed
YOM HASTUDENT
05.6.2002
Tirgul:
Discussion of homework.
Status of projects
Euclidean Algorithm for polynomials.
Multiple roots of polynomials.
Theorem: A polynomial p(x) over the reals has multiple roots iff
p(x) and p'(x) have a common divisor.
Lecture:
Completion of proof for degree 3.
More problems NP_R complete.
More problems in P_R.
Linear problems over R.
12.6.2002
Tirgul:
Discussion of homework.
Quantifier elimination.
Complexity of quantifier elimination.
Lecture:
NP_Z is not computable.
Reduction to Matysevich's theorem.
Outline of proof Matyasevich's theorem
P_Z is different from NP_Z.
19.6.2002
Tirgul:
Discussion of homework.
Lecture:
Counting problems and the class #P in the Turing models.
See lecture one of
of the course "Combinatorial counting",
236 605 (Spring 2001).
Slides
26.6.2002
Tirgul:
Repetition of #P
Lecture:
Valiant's model of computation, VP and VNP,
Examples.
See lecture two of
of the course "Combinatorial counting",
236 605 (Spring 2001).
Slides .
Outlook and research problems:
-
Unify BSS and VP/VNP and Metafinite modeltheory of
Graedel-Gurevich.
-
Generalize #P and VNP and make it work in BSS.
-
Develop descriptive complexity in BSS further.