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[1]$-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
• 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
• While this may not be a formal implication, it seems like the natural techniques to try to show that it is W[1]-hard would also show that MCSP is NP-hard, which is currently unknown (and some think unlikely). Would be nice to make the connection formal... – Joshua Grochow Nov 20 '19 at 6:21
• @JoshuaGrochow I finally had a chance to think about this. I think that if the above problem is W[1]-hard under parameter preserving reductions (defined in "Survey of parameter-preserving reductions" by Philipp Kuinke), then MCSP is NP-hard. – Michael Wehar Feb 10 at 21:27