<p>In Downey and Fellows' 2013 book (<i>Fundamentals of Parameterized Complexity</i>; 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.</p>

<p>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.</p>

<p>For an overview of some basic connections, you could have a look at a report that I wrote: <a href="https://eccc.weizmann.ac.il/report/2015/130/" rel="noreferrer">An Overview of Non-Uniform Parameterized Complexity</a>.</p>

CC BY-SA 3.0
2017-09-20T09:02:59.563Z
2017-09-20T09:02:59.563Z
Ronald de Haan
<p><strong>Getting Started</strong></p>

<p>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}}$.</p>

<p><strong>Definitions</strong></p>

<p>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.</p>

<p>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.</p>

<p><em>Remark:</em> 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.</p>

<p><strong>Question</strong></p>

<p>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$?</p>

<p><strong>A More High-level Question</strong></p>

<p>Does uniform vs non-uniform parameterized complexity have any relationship to uniform vs non-uniform circuit complexity?</p>

<cc.complexity-theory><circuit-complexity><parameterized-complexity><structural-complexity>
Are there any parameterized problems in non-uniform FPT that are suspected (but not proven) to be in uniform-FPT?
Michael Wehar
# Are there any parameterized problems in non-uniform FPT that are suspected (but not proven) to be in uniform-FPT?

(Asked by: username_0 on 2017-09-17)

**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?

**Tags:** cc.complexity-theory, circuit-complexity, parameterized-complexity, structural-complexity

---

## 1 answers

### Answer by username_1 on 2017-09-20. Score: 6 | Accepted answer

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](https://eccc.weizmann.ac.il/report/2015/130/).


---

