Parameterized Computation and Applications

P和NP的定义是基于多项式时间计算的。人们是否应该把一个计算复杂性为Q(N100)的问题称为“可处理的”，这一直是一个令人担忧的问题。一种普遍接受的解释是，在实践中，P中的大多数问题实际上都可以在O(N3)或更短的时间内解决。然而，最近的研究表明，一些非常重要的实际问题似乎需要算法的复杂性仅限于非常高次多项式。另一方面，有许多以参数形式描述的NP-Hard问题，它们需要确定性地构造精确解，而广泛的应用只对具有较小或中等参数值的问题感兴趣。重点是如何利用这一事实，在实践中开发出最有效的算法来解决这些棘手的问题。本研究基于最近发展起来的参数化复杂性理论，研究了易处理和难处理分类的精化，目的是识别实际问题的不实用的多项式时间算法和有效的指数时间算法。研究了算法理论中的以下几个具体问题：为棘手问题开发高效的参数化算法。这包括两个步骤：识别固定参数可处理问题，并开发最有效的参数化算法；基于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.