Return to search

Vlastnosti intervalových booleovských funkcí / Properties of interval Boolean functions

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

Identiferoai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:341200
Date January 2014
CreatorsHušek, Radek
ContributorsČepek, Ondřej, Kučera, Petr
Source SetsCzech ETDs
LanguageCzech
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/masterThesis
Rightsinfo:eu-repo/semantics/restrictedAccess

Page generated in 0.0016 seconds