22
$\begingroup$

Is there any plausible complexity/crypto hypothesis that rules out the possibility that polynomial size circuits have subexponential-size (i.e. $2^{O(n^\epsilon)}$ with $\epsilon<1$) bounded-depth ($d = O(1)$) circuits?

We know that every function computable by a $\mathsf{NC^1}$ circuit can be computed by a size $2^{O(n^\epsilon)}$ depth $d$ circuit (using AND, OR, and NOT gates, unbounded fan-in) (for every $0 <\epsilon$ there is a $d$ and $d$ can be taken to be $O(1/\epsilon)$).

The question is:

is there a reason that would make the existence of such circuits for general polynomial size circuits unlikely?

Improve this question
$\endgroup$
9
  • 3
    $\begingroup$ If by subexponential-size you mean $2^{n^{o(1)}}$ (rather than $2^{o(n)}$) and by bounded-depth you mean constant depth, then parity does not have subexponential-sized bounded-depth circuits under no assumptions. $\endgroup$
    – Mahdi Cheraghchi
    Oct 27, 2011 at 18:18
  • $\begingroup$ You should post your comment as an answer. You'll get credit for it, and if appropriate it can be marked as an accepted answer. This will also prevent the question from being automatically reposted periodically by the Community bot. $\endgroup$
    – Suresh Venkat
    Oct 27, 2011 at 18:25
  • $\begingroup$ @MCH, I updated the question to clarify what I mean by subexponential size. $\endgroup$
    – Kaveh
    Oct 27, 2011 at 22:19
  • 3
    $\begingroup$ In the uniform case, you can say something ($TIME(t) \subseteq \Sigma_{O(d)}TIME[n^{1/d}]$ implies time lower bounds for SAT). But in the non-uniform case, we know no strong lower bounds for P/poly, and no strong lower bounds for your definition of sub-exponential size constant-depth circuits. E.g. it's still possible $EXP^{NP}$ could be simulated in either of these classes. So I am not sure what you could conclude. (Why did I make this a comment? Because it's not really an answer...) $\endgroup$
    – Ryan Williams
    Oct 28, 2011 at 3:39
  • 2
    $\begingroup$ Well, $TIME(t) \subseteq ATIME(t^{1-\epsilon})$ is considered unlikely. Sipser (CCC' 86) showed that either $P = RP$ or $TIME(t) \subseteq SPACE(t^{1-\epsilon})$ for some $\epsilon > 0$, under certain expander construction hypotheses that were later shown to be true by Saks, Srinivasan, and Zhou.This was taken as evidence that $P = RP$. Later work on hardness vs randomness made the connections more precise. $\endgroup$
    – Ryan Williams
    Nov 11, 2011 at 21:42

1 Answer 1

Reset to default
8
+150
$\begingroup$

What you ask for should have bad consequences but I cannot think of any immediately. So I have only some pointers to what we know.

Check out Viola's On the power of small depth computation The best we know is Valiant's construction for boolean circuits: log depth linear sized circuits to depth 3 subexp circuits. (We know better for arithmetic circuits.) There are also some results of Beigel/Tarui on ACC begin contained in bounded depth circuits of superpoly size. I don't recall it being extended to all of $NC^1$ though.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the interesting pointers. I am mainly interested on the likeliness of the existence of such simulation (i.e. conjectures and hypothesis that would imply a negative or positive answer for $\mathsf{P/poly}$ and similar classes like $\mathsf{NC}$ where the answer is not known unconditionally.) Do we know anything like that? $\endgroup$
    – Kaveh
    Oct 28, 2011 at 11:14
  • $\begingroup$ Unfortunately, nothing. I was thinking of some of the old papers by Buhrman/Homer and others but don't remember anything of this sort. Will get back if something turns up. $\endgroup$
    – V Vinay
    Oct 28, 2011 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.