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