Sabancı University Mathematics Colloquium

P/NP Dichotomy for Finite Quandles
Robert McGrail
Bard College, United States of America
Özet : 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.
  Tarih : 22.03.2018
  Saat : 13:40
  Yer : FENS-L055
  Dil : English