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?

  • $\begingroup$ 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. $\endgroup$ – Michael Wehar Jan 13 '19 at 20:32

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.