Einladung zum Informatik-Kolloquium

======================================

Datum und Zeit: Dienstag, 2. Oktober 2012 - 14:15 Uhr

Raum: 123, Oettingenstraße 67

Es spricht: Prof. Antonina Kolokolova, Memorial University of Newfoundland

Über: How hard is proving hardness? A logic approach to barriers in complexity.

Abstract:

In spite of much work over the years, the main questions in complexity theory such as P vs. NP remain unresolved.  Is this question solvable at all? Is P vs. NP independent of some logical theory? Indeed, on  a meta-level, there are several results that state that certain classes of techniques, including Turing's celebrated diagonalization, cannot be used to resolve these questions. Such results we call the "barriers" of complexity theory.

In this talk, we will survey some of the main such barriers (Relativization, Natural Proofs, Algebrization),  and talk about how knowledge of such barriers helps evaluate (and, so far, discard) proposed proofs of P vs. NP.  We will talk about the logic basis for such barriers, where a barrier means an independence of a logic theory.