Fully symmetric operations

• Thesis title in Czech: Úplně symetrické operace
• Thesis title in English: Fully symmetric operations
• Key words: symetrické termové operace|problém splnitelnosti omezujících podmínek|lineární programování
• English key words: symmetric term operations|constraint satisfaction problem|linear programming
• Academic year of topic announcement: 2023/2024
• Thesis type: Bachelor's thesis
• Thesis language: angličtina
• Department: Department of Algebra (32-KA)
• Supervisor: prof. Mgr. Libor Barto, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 23.10.2023
• Date of assignment: 23.10.2023
• Confirmed by Study dept. on: 26.10.2023
• Date and time of defence: 05.02.2025 09:00
• Date of electronic submission: 09.01.2025
• Date of submission of printed version: 09.01.2025
• Date of proceeded defence: 05.02.2025
• Opponents: Dmitrii Zhuk, Ph.D.

Guidelines

The Constraint Satisfaction Problem over an algebra A is solvable by the basic linear programming relaxation if, and only if, A has a fully symmetric term operation of every arity. It is, however, unclear how to decide that the latter condition is satisfied for a given algebra. The goal of the thesis is make a progress toward answering this decidability question.

References

L. Barto, J. Bulin, A. Krokhin, J. Oprsal, Algebraic approach to promise constraint satisfaction, Journal of the ACM 68/4 (2021), 1-66
L. Barto, A. Krokhin, R. Willard, Polymorphisms, and how to use them, in "The Constraint Satisfaction Problem: Complexity and Approximability", Dagstuhl Follow-Ups, vol. 7, 1–44, 2017