Parameterized Computation and Applications

P和NP的定义是基于多项式时间计算的。一个计算复杂度为Q （n100）的问题是否应该被称为“可处理的”，这是一个长期关注的问题。一个普遍接受的解释是，在实践中，P中的大多数问题实际上可以在时间0 （n3）或更短的时间内解决。然而，最近的研究表明，一些非常重要的实际问题似乎需要算法，其复杂性仅受非常高次多项式的限制。另一方面，有许多np困难问题，以参数化的形式描述，人们希望确定地构造精确的解，而广泛的应用只对这些参数值较小或中等的问题的求解感兴趣。关键是如何利用这一事实，并在实践中为这些棘手的问题开发出最有效的算法。本研究基于最近发展的参数化复杂性理论，对可跟踪性和难处理性的分类进行了细化，目的是找出实际问题中“不实用”的多项式时间算法和“有效”的指数时间算法。本文主要研究了算法理论中的以下几个具体问题：针对棘手问题开发高效的参数化算法。这包括两个步骤：确定固定参数可处理的问题，以及为这些问题开发最有效的参数化算法。识别“硬”多项式时间可解问题，基于w[1]-硬度框架。在此框架下，还将研究其他实践中的问题。研究参数化复杂度与逼近性之间的关系。参数化复杂性为证明某些优化问题的非逼近性提供了新的技术，这些问题在经典复杂性理论的基础上可能不容易甚至不可能实现。

The definitions of P and NP are based on polynomial time computations. It has been a long-time concern whether one should call a problem with computational complexity Q (n100) 'tractable". A commonly accepted explanation is that in practice most problems in P in fact can be solved in time O(n3) or better. However, recent research has shown that some very important practical problems seem to require algorithms whose complexity is bounded only by very high degree polynomials. On the other hand, there are many NP-hard problems, described in a parameterized version, for which it is desired to construct the precise solutions deterministically, while a wide range of applications is only interested in solving these problems with a small or moderate value for the parameters. The point is how to take advantage of this fact and develop most efficient algorithms for these intractable problems in practice.The research studies the refinement of the classification of tractability and intractability, based on the recently developed theory of parameterized complexity, with the aim of identifying "impractical" polynomial time algorithms and "efficient" exponential time algorithms for practical problems. The following specific issues in algorithm theory are investigated:developing efficient parameterized algorithms for intractable problems. This includes two steps: identifying fixed-parameter tractable problems, and development of most efficient parameterized algorithms for the problems.identifying "hard" polynomial time solvable problems, based on the framework of the W[1]-hardness. Problems from other practice will also be studied based on this framework.investigating the relationship between parameterized complexity and approximability. Parameterized complexity suggests new techniques for proving non-approximability for certain optimization problems that may otherwise be not easy or even impossible based on classical complexity theory.