2016/12/21 by Aida Gainutdinova, Gainutdinova, Aida, Abuzer Yakaryılmaz +1
Computer Science · Engineering · #Coding theory and cryptography #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Formal Languages and Automata Theory (cs.FL) #Quantum Physics (quant-ph) #graph theory and CDMA systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1612.07015
openalex publication_date 2016/12/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.