摘要 Abstract
近期引入的一种用于衡量布尔函数复杂性的指标——析取复杂度(DC)——与其他复杂性度量进行了比较:流算法的空间复杂性和非确定性分支程序(NBP)的复杂性。我们证明了DC与NBP不可比。具体而言,我们给出一个具有低NBP但具有次指数DC的函数。相反,基于计算复杂性猜想,我们提供了论据,表明在某些情况下DC可以比NBP至少超多项式增长。此外,我们证明了单调版本的NBP复杂性严格弱于DC。我们还证明了一次遍历流算法的空间复杂性严格弱于DC。进一步地,我们引入了流算法的一个推广形式,该形式能够捕捉到DC的全部能力。这种推广可以用不可逆地向布尔向量的条目写入1的非确定性算法来表达(即不允许从1变为0)。最后,我们讨论了析取复杂度中的一个不寻常现象:均匀硬函数的存在。这些函数具有其析取复杂性最大化的特性,并且这一特性扩展到了所有被它们支配的函数。
A recently introduced measure of Boolean functions complexity--disjunc\-tive complexity (DC)--is compared with other complexity measures: the space complexity of streaming algorithms and the complexity of nondeterministic branching programs (NBP). We show that DC is incomparable with NBP. Specifically, we present a function that has low NBP but has subexponential DC. Conversely, we provide arguments based on computational complexity conjectures to show that DC can superpolynomially exceed NBP in certain cases. Additionally, we prove that the monotone version of NBP complexity is strictly weaker than DC. We prove that the space complexity of one-pass streaming algorithms is strictly weaker than DC. Furthermore, we introduce a generalization of streaming algorithms that captures the full power of DC. This generalization can be expressed in terms of nondeterministic algorithms that irreversibly write 1s to entries of a Boolean vector (i.e., changes from 1 to 0 are not allowed). Finally, we discuss an unusual phenomenon in disjunctive complexity: the existence of uniformly hard functions. These functions exhibit the property that their disjunctive complexity is maximized, and this property extends to all functions dominated by them.