Reading Seminar
Jalex Stark,
We will introduce the finite model approach, showing that graph properties which are easily decided by a Turing machine are defined by simple formulae and vice versa. We'll use this idea to give a full logical characterization for NP, and then we'll discuss why such a characterization is much harder to obtain for P.
For more information, please contact Martino Lupini by email at [email protected] or visit Finite Models and Fagin's Theorem.
Event Sponsors