Parameterized Computation and Applications

P和NP的定义基于多项式时间计算。 长期以来，人们一直关注是否应该将计算复杂度为Q（n100）的问题称为“可处理的”。 一个普遍接受的解释是，在实践中，P中的大多数问题实际上可以在O（n3）或更好的时间内解决。 然而，最近的研究表明，一些非常重要的实际问题似乎需要的算法，其复杂性是有限的，只有非常高的次数多项式。 另一方面，有许多NP难问题，在参数化的版本中描述，对于这些问题，希望确定性地构造精确的解，而广泛的应用只对解决这些问题感兴趣，这些问题的参数值很小或适中。 问题的关键是如何利用这一事实，并制定最有效的算法，这些棘手的问题在practic.The研究的基础上，最近发展起来的参数化复杂性理论，研究的分类的精细化，以确定“不切实际的”多项式时间算法和“有效的”指数时间算法的实际问题。 算法理论中的以下具体问题进行了研究：开发有效的参数化算法的棘手问题。 这包括两个步骤：识别固定参数易处理的问题，并开发最有效的参数化算法的问题。识别“硬”多项式时间可解的问题，基于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.