Development of Grapy Theoretical Analysis for Proof Complexity

证明复杂性的 Grapy 理论分析的发展

• 批准号: 22800033
• 负责人: SETO Kazuhisa
• 金额: $ 1.67万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Research Activity Start-up
• 财政年份: 2010
• 资助国家: 日本
• 起止时间: 2010 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-22800033/
• 关键词: 計算量理論; グラフ理論; 証明複雑さ; Hajos Calculus; 列挙; 彩色問題

NP versus coNP problem is one of the fundamental open problems intheoretical computer science. To study proof complexity is the main approach to resolve this problem. In previous works, many researches have been done on proof systems for Boolean functions, but we studied proof complexity via graph calculus, mainly Hajos Calculus. We obtained the relationship between the complexity of proof systems and that of graph calculus. Moreover, we can implement an enumeration algorithm generating non-3-colorable graphs. This algorithm simulates a part of Hajos Calculus for planar graphs.

NP对coNP问题是理论计算机科学中的一个基本开放问题。研究证明复杂性是解决这一问题的主要途径。在以往的工作中，已经做了很多的研究，证明系统的布尔函数，但我们研究的证明复杂性，通过图演算，主要是Hajos演算。得到了证明系统的复杂性与图演算的复杂性之间的关系。此外，我们可以实现一个枚举算法生成非3-着色图。该算法模拟了平面图Hajos演算的一部分。

项目成果

A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis

完全二元基础公式的可满足性算法和平均情况硬度

• 发表时间: 2012
• 期刊: Proceedings of the 27th IEEE Conference on Computational Complexity
• 作者: K.Seto;S.Tamaki
• 通讯作者: S.Tamaki

ホームページ

主页

A Satisfiability Algorithm for Formulas over the Full Binary Basis

完全二元基础公式的可满足性算法

• 发表时间: 2012
• 作者: K.Seto;S.Tamaki
• 通讯作者: S.Tamaki

Improved Randomized Algorithms for 3-SAT

改进的 3-SAT 随机算法

• 发表时间: 2010
• 期刊: Proceedings of the 21^<st> International Symposium on Algorithms and Computation, LNCS
• 作者: K.Iwama;K.Seto;T.Takai;S.Tamaki
• 通讯作者: S.Tamaki

The Planar Hajos Calculus for Bounded Degree Graphs

有界度图的平面 Hajos 演算

• 发表时间: 2010
• 期刊: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E93-A(6)
• 作者: K.Iwama;K.Seto;S.Tamaki
• 通讯作者: S.Tamaki