Fully symmetric operations

• Název práce v češtině: Úplně symetrické operace
• Název v anglickém jazyce: Fully symmetric operations
• Klíčová slova: symetrické termové operace|problém splnitelnosti omezujících podmínek|lineární programování
• Klíčová slova anglicky: symmetric term operations|constraint satisfaction problem|linear programming
• Akademický rok vypsání: 2023/2024
• Typ práce: bakalářská práce
• Jazyk práce: angličtina
• Ústav: Katedra algebry (32-KA)
• Vedoucí / školitel: prof. Mgr. Libor Barto, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 23.10.2023
• Datum zadání: 23.10.2023
• Datum potvrzení stud. oddělením: 26.10.2023
• Datum a čas obhajoby: 05.02.2025 09:00
• Datum odevzdání elektronické podoby: 09.01.2025
• Datum odevzdání tištěné podoby: 09.01.2025
• Datum proběhlé obhajoby: 05.02.2025
• Oponenti: Dmitrii Zhuk, Ph.D.

Zásady pro vypracování

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.

Seznam odborné literatury

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