I want to construct a depth $\mathrm{poly}(n)$ circuit computing $$f(x) = \text{first }n\text{ bit string with circuit complexity }\sqrt n$$ where $x \in \{0, 1\}^n$. I see how to do it with depth $2^n$ (have a level enumerating circuits of size at most $\sqrt n$ and OR their truth tables; then you can use AND gates to find the first OR that is a 0) but I can't get down to $\mathrm{poly}(n)$. Anyone see how?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Can you edit your question to include what definition you are using of what it means for a string $s$ to have circuit complexity $c$? $\endgroup$– D.W. ♦Commented Sep 4 at 21:16
-
2$\begingroup$ I think this might be trivial. The way you phrased your question, the answer only depends on the length of the input. In a non-uniform model, you only need circuits of depth 1: for each input size $n$, the circuit $C_n$ can ignore the input and hard-codes the output. $\endgroup$– Benjamin KuykendallCommented Sep 5 at 3:46
-
$\begingroup$ It seems to me you are confusing size and depth. I can't fully follow you description, but any sensible way of computing in parallel the truth tables of all circuits of size $\sqrt n$ in $\log n$ variables and then the lexicographically smallest among the results will have size $n^{O(\sqrt n)}$, but depth only $n^{O(1)}$. E.g., compute the $n$ output bits one by one. In fact, you can make it depth $O(\sqrt n(\log n)^2)$ or so: the smaller of two strings can be computed by a circuit of depth $O(\log n)$; arrange these into a balanced binary tree. I'm assuming fan-in 2 circuits, otherwise ... $\endgroup$– Emil JeřábekCommented yesterday
-
$\begingroup$ ... it's even more trivial. And this gives a uniform sequence of circuits; for a nonuniform sequence, you can trivially do it in depth 1 and size $n$, as Benjamin Kuykendall wrote. $\endgroup$– Emil JeřábekCommented yesterday
Add a comment
|