Variable Influences in Conjunctive Normal Forms
Variable Influences in Conjunctive Normal Forms
复制标题
连接范式中的变量影响
DOI：
10.1007/978-3-642-02777-2_12
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Patrick Traxler
中科院分区：
文献类型：
--
作者：
Patrick Traxler
我们给出了由k -cnfs定义的布尔函数的总影响的上界。我们的界几乎是最优的。我们通过扩展和适当使用Paturi， Pudlak和Zane的算法来实现它。我们还讨论了证明和计算最大子句宽度k下界的应用。
We provide an upper bound on the total influence of Boolean functions defined by k -cnfs. Our bound is nearly optimal. We achieve it by an extension and appropriate use of an algorithm of Paturi, Pudlak, and Zane. We also discuss applications to prove and compute lower bounds for the maximum clause width k .
在 STDk/3[k ;
DOI：
--
发表时间：
2008
期刊：
Discrete Mathematics 308
影响因子：
--
作者：
Y. Hiramine;C. Suetake;K. Akiyama C. Suetake
通讯作者：
K. Akiyama C. Suetake