参数复杂性、SAT求解器和树宽度

项目名称： 参数复杂性、SAT求解器和树宽度

项目编号： No.61373029

项目类型： 面上项目

立项/批准年度： 2013

项目学科： 自动化技术、计算机技术

项目作者： 陈翌佳

作者单位： 上海交通大学

项目金额： 76万元

中文摘要： 参数复杂性是目前在理论计算机科学中非常活跃的一个分支。相比以多项式时间算法为核心的经典算法和复杂性理论，通过允许超多项式行为局限于某些小参数的指数时间算法，它为算法设计提供了更多的灵活性和复杂性分析更为精细的框架。我们计划研究以下的一些基于树宽度的比较新颖的参数复杂性问题。1)SAT问题在工业界有着极为重要的应用。虽然其在一般意义上是NP难的，但许多SAT问题的求解器在实际使用中非常高效。我们计划从参数复杂性角度来分析这些SAT求解器。特别的是，我们希望理解对于实际应用中出现的SAT实例是否存在一些隐藏的参数，它们导致求解器的高效。该研究一个很好的起点就是树宽度有界的实例。2)对于很多参数计算问题，树宽度给出了高效可解和计算困难间的精确边界。但还有一些关于树宽度及其相关的算法问题仍有待解决。如：我们希望研究删点操作对树宽度的影响；针对程序语言的研究，我们试图给出树宽度有界图的公理系统；为了理解monadic二阶逻辑(MSO)的表达能力，我们计划考察独立于序的MSO。

中文关键词： 参数复杂性；固定参数可解；树宽度；近似；复杂性类

英文摘要： Parameterized complexity is a very active subfield of theoretical computer science. Compared to classical theory of algorithms and complexity which is built on the central notion of polynomial time computability, it provides more flexibility for algorithm

英文关键词： parameterized complexity；fixed-parameter tractable；treewidth；approximation；complexity classes