Establishing Computer Assisted Proof Methods for Computational Intractability

点击翻译按钮获取中文摘要

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.