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

Question

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?

Answer 1

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/~allender/papers/aht.pdf