Computational Upper and Lower Bounds via Parameterized Complexity

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

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.