Název: Monotónní funkce vyhýbající se majoritám
Překlad názvu: Monotone functions avoiding majorities
Autoři: Petr, Jan ; Barto, Libor (vedoucí práce) ; Mottet, Antoine (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2020
Jazyk: eng
Abstrakt: [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. 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
Klíčová slova: majoritní funkce; minion; minor funkce; polymorfismus; Promise Constraint Satisfaction Problem; majority function; minion; minor of a function; polymorphism; Promise Constraint Satisfaction Problem

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/119837

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-434105


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce