6533b82afe1ef96bd128b60a

RESEARCH PRODUCT

Nondeterministic Unitary OBDDs

Aida GainutdinovaAbuzer Yakaryilmaz

subject

Discrete mathematicsHierarchy (mathematics)Intersection (set theory)010102 general mathematics0102 computer and information sciencesFunction (mathematics)Computer Science::Computational Complexity01 natural sciencesUpper and lower boundsUnitary stateNondeterministic algorithmCombinatoricsNegation010201 computation theory & mathematicsBoolean operations in computer-aided design0101 mathematicsMathematics

description

We investigate the width complexity of nondeterministic unitary OBDDs (NUOBDDs). Firstly, we present a generic lower bound on their widths based on the size of strong 1-fooling sets. Then, we present classically “cheap” functions that are “expensive” for NUOBDDs and vice versa by improving the previous gap. We also present a function for which neither classical nor unitary nondeterminism does help. Moreover, based on our results, we present a width hierarchy for NUOBDDs. Lastly, we provide the bounds on the widths of NUOBDDs for the basic Boolean operations negation, union, and intersection.

yearjournalcountryeditionlanguage
2017-01-01
https://doi.org/10.1007/978-3-319-58747-9_13