Parameterized Complexity Theory
Parameterized Complexity Theory
复制标题
DOI：
10.1007/3-540-29953-x
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
J. Flum;Martin Grohe
中科院分区：
文献类型：
--
作者：
J. Flum;Martin Grohe
经典的复杂性理论根据解决问题的算法所需的资源量（通常是时间或空间）来分析和分类问题。这是一个基本的想法，可以追溯到Hartmanis和Stearns在20世纪60年代早期的工作，以衡量所需的资源数量作为投入规模的函数。这导致了可管理的各种复杂性类别和一个清晰的棘手理论。然而，仅根据输入大小来度量复杂性意味着在所得的复杂性理论中忽略关于输入实例的任何结构信息。有时，这会使问题看起来比通常更难。参数化复杂性理论则是一种倒退，它不仅用输入大小来衡量复杂性，而且还用一个参数来衡量复杂性，这个参数是一个可以以任意方式依赖于输入的数值。主要目的是解决复杂性问题的情况下，我们知道，参数是相对较小的。例如，考虑评估数据库查询的问题。它的输入有两部分，数据库和查询。注意，这两个部分的大小通常会有很大的不同;数据库将比查询大得多。这个问题的参数化复杂性分析的一个自然参数是查询的大小。作为一个更有理论动机的例子，考虑优化问题的近似方案。它们的输入由一个问题实例和一个误差界组成。一个自然参数是1/2。如果我们可以接受近似中5%的误差，则我们的近似方案的参数值为1/1 = 20。图上的许多算法问题的典型参数是输入图的树宽度或最大度。自然参数化问题的许多其他例子可以在其他应用领域中找到，例如自动验证，人工智能或计算生物学。参数化复杂性理论的核心概念是固定参数的易处理性。它放松了传统的易处理性概念，多项式时间求解-
Classical complexity theory analyzes and classifies problems by the amount of a resource, usually time or space, that is required by algorithms solving them. It was a fundamental idea, going back to the work of Hartmanis and Stearns in the early 1960s, to measure the required amount of the resource as a function of the size of the input. This has led to a manageable variety of complexity classes and a clean-cut theory of intractability. However, measuring complexity only in terms of the input size means ignoring any structural information about the input instances in the resulting complexity theory. Sometimes, this makes problems appear harder than they typically are. Parameterized complexity theory takes a step backwards and measures complexity not only in terms of the input size, but in addition in terms of a parameter, which is a numerical value that may depend on the input in an arbitrary way. The main intention is to address complexity issues in situations where we know that the parameter is comparatively small. Consider, for example, the problem of evaluating a database query. Its input has two parts, a database and the query. Observe that these two parts will usually differ in size quite significantly; the database will be much larger than the query. A natural parameter for a parameterized complexity analysis of this problem is the size of the query. As a more theoretically motivated example, consider approximation schemes for optimization problems. Their input consists of a problem instance and an error bound ϵ. A natural parameter is 1/ϵ. If we can accept an error of 5% in an approximation, we have a parameter value 1/ϵ= 20 for our approximation scheme. Typical parameters for many algorithmic problems on graphs are the tree width or the maximum degree of the input graph. Numerous other examples of naturally parameterized problems can be found in other application areas such as automated verification, artificial intelligence, or computational biology. The central notion of parameterized complexity theory is fixed-parameter tractability. It relaxes the classical notion of tractability, polynomial time solv-