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


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.


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.

  • $\begingroup$ This is great! Thank you so much. :) $\endgroup$ – Michael Wehar Sep 20 '17 at 14:23

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.