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.

Event Sponsors:

Mathematics - More events from this Sponsor

For more information, please contact Martino Lupini by email at [email protected] or visit Finite Models and Fagin's Theorem.