Abstract:
This small booklet contains the titles and abstracts of the
talks given at the workshop Proof Theory and Complexity (PTAC'98), hosted by
BRICS during the first week of August 98 (August 3 - August 7). The
topic of the workshop will be on proof-theory with connections to issues of
complexity in the widest sense including e.g.:
-
Strength (proof-theoretic and mathematical) of subsystems of second-order
arithmetic and type theories.
- Type-free applicative systems (explicit
mathematics).
- Complexity of Proof Transformations (cut-elimination,
normalization, epsilon-substitution etc.).
- Proofs as Programs.
-
Proof Interpretations and their complexity: Realizability and functional
interpretations, game theoretic and categorical interpretations.
-
Bounded arithmetic and connections to complexity theory (including feasible
arithmetic and analysis).
- Proof Complexity of propositional proof
systems: resolution, Frege systems, Nullstellensatz proofs etc.
-
Interactive and probabilistic proofs.
There were two
preparatory lectures during the week before the workshop (by E. Palmgren and
V. Orevkov--abstracts can be obtained from the BRICS homepage), and there
are two special lectures in connection with the workshop that take place
during this week (by A. Feferman and A. Wigderson)
Available as PostScript,
PDF,
DVI.
|