Algebra Seminar talk
2018-03-16 (10:15)
Manuel Bodirsky (TU Dresden)
The Dichotomy for Montone Monadic SNP via Extreme Amenability
Abstract:
A theorem of Cherlin, Shelah, and Shi asserts that for every finite class F of finite structures there exists an (up to isomorphism unique) model-complete structure U that is universal for the class of all countable structures that do not homomorphically embed any structure from F. Hubicka and Nesetril recently proved that the expansion of U by a generic linear order has the Ramsey property, and by a result of Kechris, Pestov, and Todorcevic it has an extremely amenable automorphism group.
We present an application of this result in complexity classification in theoretical computer science. Specifically, we give a new proof that the complexity class Monotone Monadic Strict NP (MMSNP) has a complexity dichotomy (P vs NP-complete) which does not rely on the involved expander constructions of Kun.
Joint work with Antoine Mottet and Florent Madelaine.