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?

  • 1
    $\begingroup$ 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... $\endgroup$ – daniello Mar 10 '17 at 11:10
  • $\begingroup$ @daniello Thank you for the kind comment! I really appreciate it. :) $\endgroup$ – Michael Wehar Mar 10 '17 at 17:41
  • $\begingroup$ 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. $\endgroup$ – Michael Wehar Mar 10 '17 at 17:43
  • $\begingroup$ 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. $\endgroup$ – Michael Wehar Mar 10 '17 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.