Princeton University
|
Computer Science 598g
|
|
Directory
General Information (this page) |What's New? | Annotated literature | Lecture notes
An introductory course to the theory of feasible
proofs in first-order systems
of bounded arithmetic and in propositional calculus. This fascinating
area is on
the border between theoretical computer science and mathematical logic
and makes
an important complement to computational complexity. The course will
not require
any background in logic, although some knowledge of complexity might
be helpful.
We will begin with a brief introduction to those
concepts and facts from
the mathematical logic that will be required during the course. Its
main body
will be naturally split into three parts:
Both the introduction and the first topic may
appear somewhat technical to
that part of the audience that is rather complexity than logical oriented.
For
the benefit of those who may want to skip them, I will try to make
the last
two topics self-contained (be prepared, however, to miss some motivations,
and,
if you are planning to skip even the first lecture, learn by yourself
what is a
classical propositional calculus). From now on I will report the progress
of the
course on-line on the What's
New? page; please consult it if you occasionally miss a
lecture or two and, of course, do not hesitate to e-mail me at razborov@cs.princeton.edu
should you need any further help. The most important announcements,
however, will
still be posted on this title page.
The class on April 10 is cancelled. Everybody is strongly encouraged to attend DIMACS workshop on Intrinsic Complexity of Computation.
Because of the conflict with the DIMACS workshop on Cryptography
and Intractability, the class on March 20 is cancelled. See you March 27.
On March 6 we will start Propositional Proof Systems
It seems that scribing lectures is on the right track now. To help this effort continue, consider signing up for one of the remaining seven lectures (on the spot).
On Feb. 28 we may start our gradual transition to the second topic, Propositional Proof Systems
Some lecture notes are available
Volunteers needed. If you feel enthusiastic about scribing several lectures of this course so that we can prepare lecture notes for public use and benefit, please let me know!
We will start Bounded Arithmetic on Feb. 14!
Undergraduate Coordinator: Tina
McCoy - 410 CS Building - 258-1746
tmhill@cs.princeton.edu