Original title: Vlastnosti intervalových booleovských funkcí
Translated title: Properties of interval Boolean functions
Authors: Hušek, Radek ; Čepek, Ondřej (advisor) ; Kučera, Petr (referee)
Document type: Master’s theses
Year: 2014
Language: cze
Abstract: [cze] [eng]
Tato práce řeší problém rozpoznávání k-intervalových boolovských funkcí. Na vstup bo- olovské funkce můžeme nahlížet jako na binární zápis přirozeného čísla. Funkce je k- intervalová, pokud - při takto interpretovaném vstupu - nabývá hodnoty jedna právě pro vstupy z daných nejvýše k intervalů. Tento problém je pro obecné boolovské funkce zadané DNF coNP-těžký. Proto se zabýváme případem, kdy DNF náleží do dané řešitelné třídy (třída je řešitelná, pokud pro DNF z ní umíme řešit falsifikovatelnost v polynomiál- ním čase a je uzavřená na částečná dosazení), a ukazujeme, že v tomto případě je úloha pro pevné k řešitelná v polynomiálním čase. 1 Boolean function f is k-interval if - input vector viewed as n-bit number - f is true for and only for inputs from given (at most) k intervals. Recognition of k-interval fuction given its DNF representation is coNP-hard problem. This thesis shows that for DNFs from a given solvable class (class C of DNFs is solvable if we can for any DNF F ∈ C decide F ≡ 1 in polynomial time and C is closed under partial assignment) and fixed k we can decide whether F represents k-interval function in polynomial time. 1
Keywords: Boolean functions; interval functions; polynomial time algorithms; booleovské funkce; intervalové funkce; polynomiální algoritmy

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/72078

Permalink: http://www.nusl.cz/ntk/nusl-494072


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses