Strong computational lower bounds via parameterized complexity

摘要: We develop new techniques for deriving strong computational lower bounds a class of well-known NP-hard problems. This includes weighted satisfiability, dominating set, hitting set cover, clique, and independent set. For example, although trivial enumeration can easily test in time O(n^k) if given graph n vertices has clique size k, we prove that unless an unlikely collapse occurs parameterized complexity theory, the problem is not solvable f(k)n^o^(^k^) any function f, even restrict parameter values to be bounded by arbitrarily small n. Under same assumption, k order @Q(@m(n)) reasonable @m, no algorithm running n^o^(^k^) k. Similar on are also derived other problems above class. Our further extended derive polynomial approximation schemes optimization distinguishing substring selection problem, which scheme been recently developed, f(1/@e)n^o^(^1^/^@e^) f theory.