Open Access. Powered by Scholars. Published by Universities.®

Algebra Commons

Open Access. Powered by Scholars. Published by Universities.®

Senior Projects Spring 2020

2020

Cayley graph

Articles 1 - 1 of 1

Full-Text Articles in Algebra

Connectedness In Cayley Graphs And P/Np Dichotomy For Quay Algebras, Thuy Trang Nguyen Jan 2020

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 …