This article is cited in 1 paper

On the complexity of computing the “Shuffled Inequality” function in classical and quantum NOBDDs

A. F. Gainutdinova

Kazan Federal University, 18 Kremlyovskaya str., Kazan, 420008 Russia

Abstract: We investigate Ordered Binary Decision Diagrams (OBDDs) — a model for computing Boolean functions. It is known that OBDD's complexity can extremely depend on the order of reading variables. There are techniques for constructing functions that do not allow choosing the optimal order for reading the input, one of which we use in this paper. A function “Shuffled Inequality” NEQS is presented, for which a lower and an upper bounds for the complexity of non-deterministic OBDD are proved. The upper bound is an improvement of a previously known result. A quantum measure-many non-deterministic OBDD is constructed that is more efficient than the classical one. The hierarchy of complexity classes defined on the basis of OBDD models is clarified.

Keywords: Ordered Binary Decision Diagram, OBDD, complexity, quantum algorithm, nondeterminism, complexity class.

UDC: 519.71

Received: 21.01.2024
Revised: 07.03.2024
Accepted: 20.03.2024

DOI: 10.26907/0021-3446-2025-1-3-14

 English version: Russian Mathematics (Izvestiya VUZ. Matematika), 2025, 69:1, 1–10