Establishing Computer Assisted Proof Methods for Computational Intractability

建立计算难解性的计算机辅助证明方法

• 批准号: 21500005
• 负责人: AMANO Kazuyuki
• 金额: $ 2.83万
• 依托单位: Gunma University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2009
• 资助国家: 日本
• 起止时间: 2009 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21500005/
• 关键词: 計算困難性; 計算機援用証明; 下界; 論理回路; 論理関数; 計算量; 決定木

The aim of this research is to establish the methods for analyzing the computational complexity in various computational models. Especially, this research pursues the use of computers as a central tool for the analysis. As a result, we obtain many significant results, of which we list some.(i) We determine the exact complexity for detecting clique structure of a graph by constant depth Boolean circuits,(ii) We develop a new method for analyzing the description length of Boolean functions in polynomial threshold representation based on computer analysis, and (iii) We determine the exact value of the maximum sensitivity of CNF formulas with bounded clause length.

本研究的目的是建立各种计算模型的计算复杂性分析方法。特别是，这项研究追求使用计算机作为分析的中心工具。结果，我们得到了许多有意义的结果，我们列出其中的一些。(i)我们确定的精确复杂度检测团结构的图的恒定深度布尔电路，（ii）我们开发了一种新的方法来分析布尔函数的描述长度的多项式阈值表示的基础上的计算机分析，（iii）我们确定的最大灵敏度的CNF公式与有界子句长度的精确值。

项目成果

Bounds on the Size of Small Depth Circuits for Approximating Majority

近似多数的小深度电路尺寸的界限

• 发表时间: 2009
• 期刊: Letcute Notes in Computer Science 5555
• 作者: Yoshinori Tanabe;Toshifusa Sekizawa;Yoshifumi Yuasa;Koichi Takahashi;Kazuyuki Amano
• 通讯作者: Kazuyuki Amano

論理関数の乱化決定木計算量について

关于逻辑函数的随机决策树的复杂性

• 发表时间: 2010
• 作者: H. Otsuki;T. Hirata;對木悟;天野一幸
• 通讯作者: 天野一幸

k-Subgraph Isomorphism on AC0 Circuits

AC0 电路上的 k 子图同构

• 发表时间: 2010
• 期刊: Computational Complexity
• 影响因子: 1.4
• 作者: 福光正幸;長谷川真吾;磯辺秀司;小泉英介;静谷啓樹;天野一幸
• 通讯作者: 天野一幸

論理関数の乱化計算機計算量について

关于干扰逻辑函数的计算复杂度

• 发表时间: 2010
• 作者: Y.Tanaka;Y.Shibata;天野一幸
• 通讯作者: 天野一幸

多項式しきい値関数密度の上界の改善

提高多项式阈值函数密度的上限

• 发表时间: 2011
• 作者: 早坂智行;天野一幸
• 通讯作者: 天野一幸