Nondeterminism and An Abstract Formulation of Nečiporuk’s Lower Bound Method
Nondeterminism and An Abstract Formulation of Nečiporuk’s Lower Bound Method
复制标题
非决定论和 Nečiporuk 下界方法的抽象表述
DOI：
--
复制
发表时间：
2016
影响因子：
0.7
通讯作者：
L. Segoufin
中科院分区：
文献类型：
--
作者：
P. Beame;Nathan Grosshans;P. McKenzie;L. Segoufin
使用此通用公式提出了Nečiporuk的下限方法的公式，比通常的复杂性特定于特定于特定的公式。尤其是对sublinear数量的非确定位，这表明，Nečiporuk的方法可用于非确定性和奇偶分支程序的大小（N3/2/logn）。
A formulation of Nečiporuk’s lower bound method slightly more inclusive than the usual complexity-measure-specific formulation is presented. Using this general formulation, limitations to lower bounds achievable by the method are obtained for several computation models, such as branching programs and Boolean formulas having access to a sublinear number of nondeterministic bits. In particular, it is shown that any lower bound achievable by the method of Nečiporuk for the size of nondeterministic and parity branching programs is at most O(n3/2/logn).