Studies on Exact Exponential Time Algorithms for Computationally Intractable Problems

许多实际的优化问题都是np困难的，这是一类计算上难以处理的问题。在本研究中，我们针对这类计算困难的问题给出了高效精确算法的设计和复杂度分析。得到了布尔电路可满足性问题和CNF最大可满足性问题的改进算法。给出了求解最小排序问题的次指数时间算法和求解约束满足问题的鲁棒算法。

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 of Boolean circuits and the CNF maximum satisfiability problem. We also gave subexponential time algorithms for the minimum arrangement problem and robust algorithms for the constraint satisfaction problems.