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