Caltech Home > PMA Home > Calendar > Reading Seminar
open search form
Tuesday, January 12, 2016
4:30 PM - 6:00 PM

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 lupini@caltech.edu or visit Finite Models and Fagin's Theorem.