On a Relation Between the Depth and Complexity of Monotone Boolean Formulas

I. S. Sergeev

首页> 外文期刊>Journal of applied and industrial mathematics >On a Relation Between the Depth and Complexity of Monotone Boolean Formulas

【24h】

On a Relation Between the Depth and Complexity of Monotone Boolean Formulas

机译：关于单调布尔公式的深度和复杂性的关系

获取原文

获取原文并翻译 | 示例

获取外文期刊封面目录资料

开具论文收录证明 >>

文献代查 >>

文献数据库（团队版） >>

页面导航

摘要
著录项
引文网络
相似文献
相关主题

摘要

We present a sequence of monotone Boolean functions whose depth over the basis {∧, ∨} is c > 1.06 times greater than the logarithm of the formula complexity.

机译：我们呈现了一系列单调布尔函数，其深度在基础上的深度为C> 1.06倍，比公式复杂性的对数大。

著录项

来源
《Journal of applied and industrial mathematics》 |2019年第4期|共7页
作者
I. S. Sergeev;
展开▼
作者单位

1Scientific and Research Institute KvantChetvyortyi Likhachyovskii per. 15125438MoscowRussia;

展开▼
收录信息
原文格式 PDF
正文语种 eng
中图分类应用数学;
关键词
Boolean formula; depth; complexity; monotone function;

机译：布尔公式;深度;复杂性;单调函数;

相似文献

外文文献
中文文献
专利

1. On a Relation Between the Depth and Complexity of Monotone Boolean Formulas [J] . I. S. Sergeev Journal of applied and industrial mathematics . 2019,第4期

机译：关于单调布尔公式的深度和复杂性的关系
2. On the Complexity and Depth of Embedded in Boolean Cube Circuits That Implement Boolean Functions [J] . S. A. Lozhkin, E. L. Dovgalyuk, O. A. Sadovnikov Moscow University Computational Mathematics and Cybernetics . 2018,第3期

机译：关于实现布尔函数的布尔立方体电路中嵌入的复杂性和深度
3. Improved Formula Size Lower Bounds for Monotone Self-Dual Boolean Functions [J] . Kenya UENO 電子情報通信学会技術研究報告. コンピュテ-ション. Theoretical Foundations of Computing . 2008,第330期

机译：单调自对偶布尔函数的改进的公式大小下界
4. Depth-Independent Lower Bounds on the Communication Complexity of Read-Once Boolean Formulas [C] . Rahul Jain, Hartmut Klauck, Shengyu Zhang Computing and combinatorics . 2010

机译：一次布尔表达式的通信复杂度的与深度无关的下界
5. Pseudo-Boolean satisfiability and quantified Boolean formulas in CAD for VLSI [D] . Mangassarian, Hratch 2008

机译：VLSI CAD中的伪布尔可满足性和量化布尔公式
6. Direct Comparison of ... formula ... and ... formula ... Cluster Projectiles in SIMS Molecular Depth Profiling [O] . Juan Cheng, Joseph Kozole, Robert Hengstebeck, -1

机译：直接比较...公式...和...公式... SIMS分子深度分析中的团簇射弹
7. On a relation between the depth and complexity of monotone Boolean formulas [O] . I. S. Sergeev 2019

机译：关于单调布尔公式的深度与复杂性的关系

On a Relation Between the Depth and Complexity of Monotone Boolean Formulas

摘要

著录项

引文网络

相似文献

相关主题

期刊订阅