Monotone functions avoiding majorities

Abstract

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. 1

V 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