Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Algebra
Connectedness In Cayley Graphs And P/Np Dichotomy For Quay Algebras, Thuy Trang Nguyen
Connectedness In Cayley Graphs And P/Np Dichotomy For Quay Algebras, Thuy Trang Nguyen
Senior Projects Spring 2020
This senior thesis attempts to determine the extent to which the P/NP dichotomy of finite algebras (as proven by Bulatov, et.al in 2017) can be cast in terms of connectedness in Cayley graphs. This research is motivated by Prof. Robert McGrail's work ``CSPs and Connectedness: P/NP-Complete Dichotomy for Idempotent, Right Quasigroups" published in 2014 in which he demonstrates the strong correspondence between tractability and total path-connectivity in Cayley graphs for right, idempotent quasigroups. In particular, we will introduce the notion of total V-connectedness and show how it could be potentially used to phrase the dichotomy in terms of connectivity for …