Design and Analysis of Algorithms for Computationally Intractable Combinatorial Problems

许多实际的优化问题都是np困难的，这是一类计算上难以处理的问题。在本研究中，我们针对这类计算困难的问题给出了高效精确算法的设计和复杂度分析。得到了求解可满足性问题和布尔连通性问题的改进算法。我们还给出了Horn-SAT的布尔连通性问题和平面图的3色性问题的复杂性表征。

Many practical optimization problems are known to be NP-hard, which is the class of computationally intractable problems. In this study, we gave design and complexity analysis of efficient exact algorithms for such computationally difficult problems. As a result, we obtained improved algorithms for the satisfiability problems (SAT) and the Boolean connectivity problems. We also gave characterizations of the complexity of the Boolean connectivity problems for Horn-SAT and the 3-colorability problems for planar graphs.