Clarification of Structural Complexity of Formula

公式结构复杂性的澄清

• 批准号: 22800032
• 负责人: UENO Kenya
• 金额: $ 2万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Research Activity Start-up
• 财政年份: 2010
• 资助国家: 日本
• 起止时间: 2010 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-22800032/
• 关键词: 論理関数; 線形計画法; 計算限界; 計算量理論; 回路計算量

We have written two papers concerned with the linear programming based method for formula size lower bounds after polishing its theoretical result. One is accepted for publication in a journal(Theoretical Computer Science), and the other is presented at an international conference(MFCS 2010). We also defined an extended formula model and give a theoretical analysis on its complexity. The paper concerned with this result is accepted and will be presented at an international conference(COCOON 2012). Furthermore, we have analyzed candidate Boolean functions towards super-quadratic formula size lower bounds and completed a paper.

我们撰写了两篇有关基于线性编程的方法的论文，用于抛光其理论结果后公式大小的下限。一个被接受在期刊（理论计算机科学）中发表，另一个被接受在国际会议上（MFCS 2010）中介绍。我们还定义了扩展公式模型，并就其复杂性进行了理论分析。与此结果有关的论文被接受，并将在国际会议上提交（Cocoon 2012）。此外，我们已经分析了候选布尔功能针对超季度公式大小的下限，并完成了纸张。

项目成果

2011年10月25日に開催された学術情報メディアセンターセミナーにおいて,「論理式の複雑さを明らかにする理論」と題し,関連する研究成果について一般向けに教育講演を行った.「科学・技術フェスタ in 京都 2011」にて高校生・大学生と議論する公開シンポジウムに参画した．

在2011年10月25日举行的学术信息与媒体中心研讨会上，我就相关研究成果向公众做了题为“揭示逻辑公式复杂性的理论”的教育讲座，并参加了公众研讨会讨论。高中生和大学生参加“京都节2011”。

Proof Methoods for Formula Siza Lower Bounds : Classics and Fyontier

公式大小下界的证明方法：经典和 Fyontier

• 发表时间: 2011
• 作者: David Avis;Kenya Ueno;Kenya Ueno;D. Avis;Kenya Ueno;D. Avis and C. Meagher;Kenya Ueno;Kenya Ueno
• 通讯作者: Kenya Ueno

Proof Methods for Formula Size Lower Bounds : Classics and Frontier

公式大小下界的证明方法：经典与前沿

• 发表时间: 2011
• 作者: David Avis;Kenya Ueno;Kenya Ueno;D. Avis;Kenya Ueno;D. Avis and C. Meagher;Kenya Ueno
• 通讯作者: Kenya Ueno

Formula Complexity of Ternary Majorities

三元多数的公式复杂性

• 发表时间: 2012
• 期刊: Proceedings of COCOON 2012, Lecture Notes in Computer Science
• 作者: D. Avis;K. Iwama;D. Paku;Kenya Ueno
• 通讯作者: Kenya Ueno

Formula Complexity of Ternary Majorities. In Proceedings of The 18th Annual International Computing and Combinatorics Conference

三元多数的公式复杂性。

• 发表时间: 2012
• 期刊: Lecture Notes in Computer Science(Springer-Verlag)
• 作者: David Avis;P.Hayden;M.Wilde;山本修一郎;山本修一郎;David Avis;山本修一郎;D. Avis;山本修一郎;山本修一郎;David Avis;山本修一郎;D. Avis;Kenya Ueno
• 通讯作者: Kenya Ueno