Parameterized Computation and Applications

参数化计算及应用

• 批准号: 0000206
• 负责人: Jianer Chen
• 金额: $ 16.78万
• 依托单位: Texas A&M Engineering Experiment Station
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-09-01 至 2004-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0000206&HistoricalAwards=false
• 关键词: Parameterized; Computation; Applications

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.

P 和 NP 的定义基于多项式时间计算。 长期以来，人们一直关心是否应该将计算复杂度为 Q (n100) 的问题称为“可处理”问题。一种普遍接受的解释是，实际上 P 中的大多数问题实际上可以在 O(n3) 或更好的时间内解决。然而，最近的研究表明，一些非常重要的实际问题似乎需要其复杂度仅受非常高次多项式限制的算法。另一方面，有许多 NP 难问题，以 参数化版本，需要确定性地构造精确的解决方案，而广泛的应用程序只对解决这些具有较小或中等参数值的问题感兴趣。 重点是如何利用这一事实，开发最有效的算法来解决实践中的这些棘手问题。本研究基于最近发展的参数化复杂性理论，研究了易处理性和难处理性分类的细化，目的是 识别针对实际问题的“不切实际”的多项式时间算法和“高效”的指数时间算法。 研究了算法理论中的以下具体问题：针对棘手问题开发有效的参数化算法。 这包括两个步骤：识别固定参数的可处理问题，以及为这些问题开发最有效的参数化算法。识别“硬”多项式时间可解 问题，基于W[1]-硬度的框架。 其他实践中的问题也将基于该框架进行研究。研究参数化复杂性和近似性之间的关系。 参数化复杂性提出了用于证明某些优化问题的不可近似性的新技术，否则根据经典复杂性理论，这些问题可能并不容易甚至不可能。