|
22 Mart 2018, 13:40 
Sabancı Üniversitesi Matematik KonuşmalarıP/NP Dichotomy for Finite Quandles Robert McGrail
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.
Cebir İngilizce FENS-L055 admin 20.03.2020 |
