- cc.complexity-theory circuit-complexity parameterized-complexity structural-complexity
- Updated Sun, 29 May 2022 12:11:34 GMT

**Getting Started**

Consider a parameterized problem $F$. We use $n$ to denote the input size and $k$ to denote the parameter. Consider the fixed levels of $F$ which we denote by $\{F_k\}_{k\in\mathbb{N}}$.

**Definitions**

We say that $F$ is in non-uniform $FPT$ if there exists a constant $c$, a function $f(k)$, and a family of algorithms $\{A_k\}_{k\in\mathbb{N}}$ such that for every $k$, $A_k$ solves $F_k$ in $O(f(k) * n^c)$ time.

We say that $F$ is in uniform $FPT$ if there exists a constant $c$ and a function $f(k)$ such that there exists a parameterized algorithm that solves $F$ in $O(f(k) * n^c)$ time.

*Remark:* One could construct unnatural examples of paramterized problems that are in non-uniform $FPT$, but are not in uniform $FPT$. For example, take an undecidable language and define the parameter $k$ to be the input length.

**Question**

Does there exist a natural parameterized problem $F$ that is proven to be non-uniform $FPT$ and suspected (yet not proven) to be uniform $FPT$?

**A More High-level Question**

Does uniform vs non-uniform parameterized complexity have any relationship to uniform vs non-uniform circuit complexity?

In Downey and Fellows' 2013 book (*Fundamentals of Parameterized Complexity*; Section 2.2), they mention an example of a problem in non-uniform FPT (Graph Linking Number) and briefly discuss that it's open whether this problem is in uniform FPT. This problem seems fairly natural.

When considering non-uniform parameterized complexity, one can look at many different variants, and many of them do have some relations to (non-uniform) circuit complexity. As far as I know, this hasn't been explored much.

For an overview of some basic connections, you could have a look at a report that I wrote: An Overview of Non-Uniform Parameterized Complexity.

External links referenced by this document: