Scholarlink

Abstract <p>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 shuffled inequality NEQS function is presented, for which a lower bound and an upper bound for the complexity of nondeterministic OBDDs are proved. The upper bound is an improvement of a previously known result. A quantum measure-many nondeterministic 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

On the Complexity of Computing the Shuffled Inequality Function in Classical and Quantum NOBDDs

  • 期刊论文

  • 发表日期：

    2025年1月1日

查看全文
  • A. F. Gainutdinova

摘要

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 shuffled inequality NEQS function is presented, for which a lower bound and an upper bound for the complexity of nondeterministic OBDDs are proved. The upper bound is an improvement of a previously known result. A quantum measure-many nondeterministic 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.