Original title:
Monotónní funkce vyhýbající se majoritám
Translated title:
Monotone functions avoiding majorities
Authors:
Petr, Jan ; Barto, Libor (advisor) ; Mottet, Antoine (referee) Document type: Bachelor's theses
Year:
2020
Language:
eng Abstract:
[eng][cze] In the past five years, the Promise Constraint Satisfaction Problem (PCSP) has been a popular topic in computational complexity, covering a wide range of computational problems. In this work, we begin by introducing the PCSP and then turn our atten- tion to the still open problem of the PCSP over 'monotone folded Boolean structures'. Brakensiek and Guruswami showed in 2016 that the PCSP is in P if all odd majorities are polymorphisms between structures under consideration. We focus on the situation in which some of the odd majorities are not among the polymorphisms. We present a technique for proving NP-completeness of PCSPs that uses the notion of heavy sets. Our approach succeeds in proving that the absence of the 3-majority makes the PCSP NP-complete. We then give a few partial results for the case of the absence of the 5-majority. We finish by determining the size of the smallest heavy set for a particular family of functions. 1V posledních pěti letech byl jedním ze zkoumaných témat výpočetní složitosti takzvaný Promise Constraint Satisfaction Problem (PCSP), který pokrývá různorodé výpočetní problémy. V této práci nejprve zavedeme PCSP a následně se zaměříme na stále otevřenou otázku výpočetní složitosti PCSP nad "monotónními folded Boolovskými strukturami". Brakensiek a Guruswami v roce 2016 dokázali, že PCSP patří do třídy P, pokud se všechny liché majority řadí mezi polymorfismy mezi námi uvažovanými strukturami. My se zaměříme se na situaci, kdy některé z majorit polymorfismy ne- jsou. Představíme si postup pro dokazování NP-úplnosti daného PCSP, který zavádí pojem "těžkých množin". Pomocí tohoto přístupu se nám podaří ukázat, že nepří- tomnost 3-majority mezi polymorfismy již implikuje NP-úplnost. Pro případ nepří- tomnosti 5-majority uvedeme několik částečných výsledků. Nakonec určíme velikost nej- menší těžké množiny pro speciální množinu funkcí. 1
Keywords:
majority function; minion; minor of a function; polymorphism; Promise Constraint Satisfaction Problem; majoritní funkce; minion; minor funkce; polymorfismus; Promise Constraint Satisfaction Problem
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/119837