<p>The Circuit Minimization Problem you describe is also known as MCSP (the Minimum Circuit Size Problem), which has been the subject of quite a few papers recently.  (I'm posting an answer to this question some 3.5 years after it was posed here.)</p>
<p>Not only is MCSP not known to be hard for P under logspace reductions; it's not even known to be hard for NL under logspace reductions.</p>
<p>The situation is somewhat better for the related problem MKTP, which is defined like MCSP, except that MKTP asks about the time-bounded Kolmogorov complexity measure KT, instead of circuit size.  More precisely, MKTP = {(x,k) : KT(x) <span class="math-container">$\le$</span> k}.  Theorems about MKTP can sometimes be viewed as suggesting what should be true for MCSP, since KT(x) is a rough approximation of the circuit size required to compute the Boolean function whose truth table is x.  MKTP is hard for the complexity class DET under (non-uniform) projections, and hence is also hard for DET under non-uniform <span class="math-container">$AC^0$</span> reductions and non-uniform logspace reductions.  In fact, MKTP is hard for a complexity class known as <span class="math-container">$NISZK_L$</span> under non-uniform projections; <span class="math-container">$NISZK_L$</span> is not believed to be contained in P, and it is not known to contain P, although it does contain DET.</p>
<p>If you don't like non-uniform reductions, then MKTP is also hard for <span class="math-container">$NISZK_L$</span> under (uniform) <em>probabilistic</em> <span class="math-container">$NC^0$</span> reductions.  But no hardness under uniform deterministic reductions is known.</p>
<p>Here are some papers that contain the relevant results:</p>
<p><a href="https://people.cs.rutgers.edu/%7Eallender/papers/niszkl.pdf" rel="noreferrer">https://people.cs.rutgers.edu/~allender/papers/niszkl.pdf</a></p>
<p><a href="https://people.cs.rutgers.edu/%7Eallender/papers/aht.pdf" rel="noreferrer">https://people.cs.rutgers.edu/~allender/papers/aht.pdf</a></p>

CC BY-SA 4.0
2023-10-12T12:02:13.580Z
Thank you so much for this!!  And, I enjoyed your talk related this at Rutgers a few years back.  I hope that you are doing well.  :)
Michael Wehar
CC BY-SA 4.0
2023-10-05T01:13:33.647Z
2023-10-05T01:13:33.647Z
Eric Allender
<p>By Circuit Minimization, I am referring to the following decision problem.  </p>

<blockquote>
  <p><strong>Circuit Minimization</strong></p>
  
  <p><strong>Input:</strong> A bit string <span class="math-container">$x$</span> and a number <span class="math-container">$k$</span>.</p>
  
  <p><strong>Question:</strong> Does there exist a Boolean Circuit <span class="math-container">$C$</span> of size at most <span class="math-container">$k$</span> that prints <span class="math-container">$x$</span>?</p>
</blockquote>

<p>By <span class="math-container">$C$</span> prints <span class="math-container">$x$</span>, I mean that the following are satisfied:</p>

<p>(1) The circuit <span class="math-container">$C$</span> has <span class="math-container">$\lceil \log_2(\vert x \vert)\rceil$</span> inputs.</p>

<p>(2) Consider lexicographically ordering bit strings of length <span class="math-container">$\lceil \log_2(\vert x \vert)\rceil$</span>.  For each <span class="math-container">$0 \leq i &lt; \vert x \vert$</span>, let <span class="math-container">$w_i$</span> denote the <span class="math-container">$i$</span>th bit string and <span class="math-container">$x_i$</span> denote the <span class="math-container">$i$</span>th bit of <span class="math-container">$x$</span>.  We have <span class="math-container">$C(w_i) = x_i$</span>.</p>

<blockquote>
  <p><strong>My Question</strong></p>
  
  <p>Is Circuit Minimization <span class="math-container">$P$</span>-hard under logspace reductions?</p>
</blockquote>

<p>I know that others have asked if this and related problems are <span class="math-container">$NP$</span>-hard, but I am wondering if it is hard for any smaller complexity classes such as <span class="math-container">$P$</span> or <span class="math-container">$L$</span> under appropriate kinds of reductions.</p>

<p>If this is an open problem, then what are the implications if it is <span class="math-container">$P$</span>-hard?</p>

CC BY-SA 4.0
2019-01-13T20:32:22.193Z
If it makes it any easier, you can consider Circuit Minimization-Search where you're given a bit string $x$, a number $k$, and a prefix $P$ for a circuit.  Then, you want to know if there exists a circuit $C$ where $C$ has size at most $k$, $C$ prints $x$, and $P$ is a prefix of $C$'s encoding.
Michael Wehar
<boolean-functions><reductions><polynomial-time><logspace><circuits>
Is Circuit Minimization $P$-hard under logspace reductions?
Michael Wehar
# Is Circuit Minimization $P$-hard under logspace reductions?

(Asked by: username_0 on 2019-01-13)

By Circuit Minimization, I am referring to the following decision problem.

> **Circuit Minimization**
>
> **Input:** A bit string $x$ and a number $k$.
>
> **Question:** Does there exist a Boolean Circuit $C$ of size at most $k$ that prints $x$?

By $C$ prints $x$, I mean that the following are satisfied:

(1) The circuit $C$ has $\lceil \log\_2(\vert x \vert)\rceil$ inputs.

(2) Consider lexicographically ordering bit strings of length $\lceil \log\_2(\vert x \vert)\rceil$. For each $0 \leq i < \vert x \vert$, let $w\_i$ denote the $i$th bit string and $x\_i$ denote the $i$th bit of $x$. We have $C(w\_i) = x\_i$.

> **My Question**
>
> Is Circuit Minimization $P$-hard under logspace reductions?

I know that others have asked if this and related problems are $NP$-hard, but I am wondering if it is hard for any smaller complexity classes such as $P$ or $L$ under appropriate kinds of reductions.

If this is an open problem, then what are the implications if it is $P$-hard?

**Tags:** boolean-functions, reductions, polynomial-time, logspace, circuits
> **Comments:**
> **username_0**: If it makes it any easier, you can consider Circuit Minimization-Search where you're given a bit string $x$, a number $k$, and a prefix $P$ for a circuit.  Then, you want to know if there exists a circuit $C$ where $C$ has size at most $k$, $C$ prints $x$, and $P$ is a prefix of $C$'s encoding.  

---

## 1 answers

### Answer by username_1 on 2023-10-05. Score: 9 | Accepted answer

The Circuit Minimization Problem you describe is also known as MCSP (the Minimum Circuit Size Problem), which has been the subject of quite a few papers recently. (I'm posting an answer to this question some 3.5 years after it was posed here.)

Not only is MCSP not known to be hard for P under logspace reductions; it's not even known to be hard for NL under logspace reductions.

The situation is somewhat better for the related problem MKTP, which is defined like MCSP, except that MKTP asks about the time-bounded Kolmogorov complexity measure KT, instead of circuit size. More precisely, MKTP = {(x,k) : KT(x) $\le$ k}. Theorems about MKTP can sometimes be viewed as suggesting what should be true for MCSP, since KT(x) is a rough approximation of the circuit size required to compute the Boolean function whose truth table is x. MKTP is hard for the complexity class DET under (non-uniform) projections, and hence is also hard for DET under non-uniform $AC^0$ reductions and non-uniform logspace reductions. In fact, MKTP is hard for a complexity class known as $NISZK\_L$ under non-uniform projections; $NISZK\_L$ is not believed to be contained in P, and it is not known to contain P, although it does contain DET.

If you don't like non-uniform reductions, then MKTP is also hard for $NISZK\_L$ under (uniform) *probabilistic* $NC^0$ reductions. But no hardness under uniform deterministic reductions is known.

Here are some papers that contain the relevant results:

[https://people.cs.rutgers.edu/~allender/papers/niszkl.pdf](https://people.cs.rutgers.edu/%7Eallender/papers/niszkl.pdf)

[https://people.cs.rutgers.edu/~allender/papers/aht.pdf](https://people.cs.rutgers.edu/%7Eallender/papers/aht.pdf)

> **Comments:**
> **username_0**: Thank you so much for this!!  And, I enjoyed your talk related this at Rutgers a few years back.  I hope that you are doing well.  :)  

---

