##### Department of Mathematics,

University of California San Diego

****************************

### Special Logic/Complexity

## Rod Downey

#### Victoria University, New Zealand

## Recent progress parametric complexity

##### Abstract:

Paramaterized Complexity looks at the time requirements for problems as a function of both instance size and other measures of the difficulty of an instance. For example, while finding an independent set of size $K$ in a graph is an $NP$-complete problem, for each fixed $K$, the problem is clearly solvable in polynomial time through exhaustive search. Parameterized complexity answers such questions as: can this problem can be solved in polynomial-time for $K$ a growing function $K(n)$; and, to what extent can the naive $n^{O(K)}$ algorithm be improved? There have been a number of very interesting connections made recently between parameterized complexity, the exponential time hypothesis (that 3SAT requires time $2^\Omega(n)$) and several other classical notions. I will discuss some of these, giving the necessary background material. If time permits I will also talk about applications to online models.

Host: Jeff Remmel

### February 8, 2005

### 1:00 PM

### AP&M 4882

****************************