2017/03/21 by Ibrahimov, Rishat, Khadiev, Kamil, Prusis, Krisjanis +2
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Formal Languages and Automata Theory (cs.FL) #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.1703.07184
We introduce the affine OBDD model and show that zero-error affine OBDDs can be exponentially narrower than bounded-error unitary and probabilistic OBDDs on certain problems. Moreover, we show that Las Vegas unitary and probabilistic OBDDs can be quadratically narrower than deterministic OBDDs. We also obtain the same results by considering the automata versions of these models.