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

<ul>
<li>Before we get started, we need the following concepts:</li>
</ul>

<p>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.  (<strong>Example:</strong> $B_7(5) = 100$)</p>

<p>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$ <strong>computes</strong> $x$ if for every $i \in [n]$, $C(B_n(i)) = x_i$.  In other words, $C$ computes $x$ one bit at a time.</p>

<ul>
<li>Now, consider the following parameterized problem:</li>
</ul>

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

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

<blockquote>
  <p><strong>Question:</strong> What is the parameterized complexity of this problem?</p>
</blockquote>

<p>This question has several parts:</p>

<ul>
<li><p>Are any more efficient algorithms known?</p></li>
<li><p>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.</p></li>
<li><p>Are there any known parameterized complexity results or conditional lower bounds for the minimum circuit size problem?</p></li>
</ul>

CC BY-SA 3.0
2017-03-10T11:10:15.877Z
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
CC BY-SA 3.0
2017-03-10T17:41:52.223Z
@daniello Thank you for the kind comment!  I really appreciate it.  :)
Michael Wehar
CC BY-SA 3.0
2017-03-10T17:43:41.543Z
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
CC BY-SA 3.0
2017-03-10T17:45:38.037Z
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
CC BY-SA 4.0
2019-11-20T06:21:02.927Z
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
CC BY-SA 4.0
2020-02-10T21:27:44.477Z
@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
<cc.complexity-theory><circuit-complexity><parameterized-complexity>
Parameterized complexity of deciding if a string can be computed by circuits of size $k\log(n)$
Michael Wehar
# Parameterized complexity of deciding if a string can be computed by circuits of size $k\log(n)$

(Asked by: username_0 on 2017-03-10)

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?

**Tags:** cc.complexity-theory, circuit-complexity, parameterized-complexity
> **Comments:**
> **username_1**: 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...  
> **username_0**: @daniello Thank you for the kind comment!  I really appreciate it.  :)  
> **username_0**: 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.  
> **username_0**: 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.  
> **username_2**: 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...  
> **username_0**: @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.  

---

## 0 answers

