Parameterized complexity of deciding if a string can be computed by circuits of size $k\log(n)$

In the following, we will describe what seems to be a parameterized version of the minimum circuit size problem (MCSP).

• Before we get started, we need the following concepts:

For every natural number $n$, consider a function $B_n: [n] \rightarrow \{0,1\}^{\lceil \log(n) \rceil}$ such that $B_n(i)$ is the $i$th bit string in $\{0,1\}^{\lceil \log(n) \rceil}$ according to the lexicographical ordering. (Example: $B_7(5) = 100$)

Now, let a bit string $x$ of length $n$ be given. Let a boolean circuit $C$ with $\lceil \log(n) \rceil$ inputs and $1$ output be given. We say that $C$ computes $x$ if for every $i \in [n]$, $C(B_n(i)) = x_i$. In other words, $C$ computes $x$ one bit at a time.

• Now, consider the following parameterized problem:

Given a bit string $x$ of length $n$ and a natural number $k$, does there exist a boolean circuit $C$ of size at most $k \log(n)$ that computes $x$?

If there are only $g(n,k)$ circuits of size $k\log(n)$, then we can solve this problem in roughly $n * k\log(n) * g(n,k)$ time by trying every possible circuit and evaluating each one on all $n$ inputs.

Question: What is the parameterized complexity of this problem?

This question has several parts:

• Are any more efficient algorithms known?

• Is this problem related to any standard parameterized complexity classes? For example, the problem could be $FPT$. Or, it could be $W$-hard or harder.

• Are there any known parameterized complexity results or conditional lower bounds for the minimum circuit size problem?

• Nice question! It might depend on what you mean by the "size" of the circuit [whether you count gates or wires, or bit size in some way]. Seems very unlikely to be FPT to me... – daniello Mar 10 '17 at 11:10
• @daniello Thank you for the kind comment! I really appreciate it. :) – Michael Wehar Mar 10 '17 at 17:41
• Yes, the notion of circuit size could make a difference. Let's say that size means the "bit size". That is, the length of the binary encoding of the circuit. – Michael Wehar Mar 10 '17 at 17:43
• In this case, $g(n,k) = n^k$ and we at least know that the problem lies in $XP$. Further, one could show that it lies in $W[P]$. But, I'm hoping someone out there might be able to show more. – Michael Wehar Mar 10 '17 at 17:45