Establishing Computer Assisted Proof Methods for Computational Intractability

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

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.