**Speaker:** Robert McGrail

**Title: **P/NP Dichotomy for Finite Quandles

**Date/Time:** Thursday, 22 March @ 13:40 pm

**Place:** FENS - L055

You are cordially invited to attend the colloquium given by Robert McGrail (Bard College, NY) on Thursday, 22 March 2018, in FENS-L055 at 1.40 pm.

**Abstract:** In the 1990's, Jeavons showed that every finite algebra corresponds to a class of constraint satisfaction problems. Vardi later conjectured that idempotent algebras exhibit P/NP dichotomy: Every non NP-complete algebra in this class must be tractable. The speaker demonstrates that dichotomy in finite quandles follows from a very strong notion of connectivity in Cayley graphs. Moreover, P/NP membership is first-order axiomatizable in an important subclass of quandles.

**Contact:** Yasemin Şengül Tezel