Title: On the Subexponential Time (In)Computability of Some NP-hard Problems
Speaker: Ge (Frank) Xia, Lafayette College
Date: April 18, 2006 2:00-3:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
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.