Title: On the Subexponential Time (In)Computability of Some NP-hard Problems

Speaker: Ge (Frank) Xia

Abstract:

In this talk, we present several interesting reductions between
several different versions of CIRCUIT SATISFIABILITY. They differ
from ordinary reductions in that they take subexponential time. From
these reductions, we show that the subexponential computability of
CIRCUIT SATISFIABILITY is closely related to the realm of
parameterized computational complexity. In particular, we show that
CIRCUIT SATISFIABILITY cannot be solved in subexponential time
unless unlikely collapses occur in parameterized complexity. Similar
lower bounds on the computational complexity are also derived for
other well-known NP-hard problems including CLIQUE, INDEPENDENT SET,
DOMINATING SET, HITTING SET, SET COVER and others. For instance,
although a trivial enumeration can easily test in time O(n^k)
whether 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)n^{o(k)} for any
function f.

This is a joint work with Jianer Chen, Benny Chor, Mike Fellows,
Xiuzheng Huang, David Juedes, and Iyad Kanj.