Computational Upper and Lower Bounds via Parameterized Complexity

通过参数化复杂度计算上限和下限

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

Many well-known NP-hard problems can be solved by straightforward enumeration algorithms of running time O(nk). For example, the clique problem (determine if a given graph of n vertices has a clique of k vertices) can be solved in time O(nk) by simply enumerating all subsets of k vertices in the graph. Based on the widely accepted assumptions in parameterized complexity theory, this proposed research will develop powerful new lower bound techniques to prove that the above enumeration algorithms are essentially the best possible solutions for a large group of well-known NP-hard problems. For example, it will be proved that the clique problem requires time n(k) even if one restricts the parameter values k to be of the order of any fixed function (n) n/ log n. The lower bound techniques will also provide new methods for the study of the trade-off between approximation ratio and running time of approximation algorithms, and for deriving computational lower bounds on polynomial time approximation schemes for certain NP-hard problems, in particular for some problems arising in computational biology. New design and analysis techniques for the development of improved algorithms will also be investigated for well-known parameterized problems with important applications in the real-world of computing. The intellectual merit of the proposed activity. Computational lower bounds have been one of the most difficult topics in the study in theoretical computer science. The proposed research will tackle this difficult problem by introducing a new methodology based on parameterized complexity theory, by which computational lower bounds on well-known NP-hard problems can be effectively derived. The research will also study new design and analysis techniques for the development of improved algorithms for important parameterized problems in practical applications. Our research agenda is motivated by, and will build on, the success we have already achieved recently in our current study on parameterized computation and complexity. The proposed research will significantly advance the understanding on the concepts of computational tractability and computational intractability, from both theoretical and practical points of view. The broader impacts resulting from the proposed activity. Progress made in this proposed research will have significant impact in education, science, and computational technology. First of all, the proposed research will be expected to strongly interact on other research fields in science and engineering, leading to collaborations of interdisciplinary research in Texas A&M University. The project will establish an excellent environment to broaden students' knowledge and research experience, benefit the undergraduate and graduate students from all areas involved in the research, and encourage underrepresented minorities and women to participate in advanced research. The results produced by the proposed research will enhance the undergraduate and graduate curriculum in computer science education.

许多众所周知的np困难问题可以通过运行时间为O（nk）的简单枚举算法来解决。例如，团问题（确定给定的n个顶点的图是否有k个顶点的团）可以通过简单地枚举图中k个顶点的所有子集在O（nk）时间内解决。基于参数化复杂性理论中被广泛接受的假设，本研究将开发强大的新下界技术，以证明上述枚举算法本质上是一大批众所周知的np困难问题的最佳可能解决方案。例如，将证明，即使将参数值k限制为任意固定函数(n) n/ log n的阶，团问题也需要时间n(k)。下界技术还将为研究近似算法的近似比率和运行时间之间的权衡提供新的方法，并为某些np困难问题的多项式时间近似方案的计算下界推导提供新的方法。特别是在计算生物学中出现的一些问题。新的设计和分析技术的发展改进算法也将研究众所周知的参数化问题在计算的现实世界中的重要应用。所提议的活动的智力价值。计算下界一直是理论计算机科学研究中最困难的课题之一。本研究将引入一种基于参数化复杂性理论的新方法来解决这一难题，该方法可以有效地推导出已知np困难问题的计算下界。该研究还将研究新的设计和分析技术，以开发用于实际应用中重要参数化问题的改进算法。我们的研究议程的动机是，并将建立在我们最近在参数化计算和复杂性的研究中已经取得的成功的基础上。所提出的研究将从理论和实践的角度大大促进对计算可跟踪性和计算难处理性概念的理解。拟议活动所产生的更广泛影响。这项研究的进展将对教育、科学和计算技术产生重大影响。首先，拟议的研究将有望与科学和工程的其他研究领域产生强烈的互动，从而导致德克萨斯农工大学的跨学科研究合作。该项目将建立一个良好的环境，以扩大学生的知识和研究经验，使本科生和研究生受益于研究涉及的各个领域，并鼓励少数民族和妇女参与先进的研究。建议研究的结果将有助提升计算机科学教育的本科及研究生课程。