# Is Circuit Minimization $P$-hard under logspace reductions?

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?

• 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 Jan 13 '19 at 20:32