joint work with Anuj Dawar, Erich Graedel, Bjarki Holm, Wied Pakusa) - continuatio
- Speaker(s)
- Eryk Kopczyński
- Affiliation
- Uniwersytet Warszawski
- Date
- March 21, 2012, 2:15 p.m.
- Room
- room 5870
- Seminar
- Seminar Automata Theory
The quest for a logic for PTIME is one of the central open problems in
both finite model theory and database theory. Specifically, it asks
whether there is a logic in which a class of finite structures is
expressible if, and only if, membership in the class is decidable in
deterministic polynomial time. After extending the first order logic
with fix point operators (which correspond to recursion) and counting,
there are still some problems which can be solved in polynomial time,
but are not expressible in our logic. It turns out that most of these
problems reduce to some kind of algebraic questions. Is the given system
of linear equations solvable? What is the rank of the given matrix?
Thus, the natural next step is to try to extend our logic with
quantifiers which answer such questions.
In the talk I will give a general introduction to logics which capture parts of PTIME, and some of the current results regarding such logics with algebraic operators.
In the talk I will give a general introduction to logics which capture parts of PTIME, and some of the current results regarding such logics with algebraic operators.