12
$\begingroup$

Do we know that the $\mathsf{TC^0}$ hierarchy does not collapse ($\mathsf{TC^0_d} \subsetneq \mathsf{TC^0_{d+1}}$ for all $d$)?

The Zoo entry for $\mathsf{TC^0}$ only mentions the separation between depth 2 and 3.

Also is there a standard reference for the fact that $\mathsf{AC^0_d}$ hierarchy does not collapse?

$\endgroup$
  • 1
    $\begingroup$ A related question would be, how many distinct functions are there in $AC_d^0$ / $TC_d^0$ ? A reasonable lower bound on these quantities would answer your questions. Also a proof of tightness for Hastad's switching lemma would perhaps answer your second question. $\endgroup$ – MCH Jun 11 '13 at 18:34
  • 4
    $\begingroup$ For the second question, I believe it was first proved in Sipser's STOC '83 paper "Borel sets and circuit complexity". This only gives super-polynomial lower bounds though. The first exponential lower bounds were given by Yao, later improved by Håstad. $\endgroup$ – Robin Kothari Jun 11 '13 at 19:03
  • $\begingroup$ @MCH, did you mean to write $\mathsf{TC^0_d}/\mathsf{AC^0_d}$? Or do you mean the number of equivalence classes of problems in $\mathsf{TC^0_d}$ w.r.t. $\mathsf{AC^0_d}$ reductions? $\endgroup$ – Kaveh Jun 11 '13 at 21:34
  • 2
    $\begingroup$ What I mean is very simple: How many distinct functions can the class of $AC_d^0$ circuits of size $s$ represent? (We can estimate the number of circuits very easily but we should be careful that some of them may compute the same function.) Once you show that this quantity grows with $d$, you are done. $\endgroup$ – MCH Jun 12 '13 at 17:53
  • 2
    $\begingroup$ @Dilworth, nonuniform. Counting doesn't seem to work, otherwise as I noted below we could then separate $\mathsf{TC^0}$ from $\mathsf{NC^1}$ which is open. $\endgroup$ – Kaveh Jul 24 '13 at 13:36
14
$\begingroup$

We know of no good lower bounds (meaning, say, a superpolynomial lower bound for a language in $\mathsf{NEXP}$) for depth 2 threshold circuits (unbounded weights). Depth 3 circuits built from majority gates, i.e. $\mathsf{TC}^0_3$ contains this class, and thus we know no good lower bounds for this class either.

$\endgroup$
  • $\begingroup$ This answers my question. Thank you Kristoffer. $\endgroup$ – Kaveh Jun 11 '13 at 21:46
  • $\begingroup$ As I wrote in the comment above, even if a problem in NEXP is not known to be outside TC$^0_2$, isn't it still possible that the non-uniform TC$^0$ hierarchy is proper via a counting argument lower bound? $\endgroup$ – Dilworth Jul 24 '13 at 13:28
  • $\begingroup$ Also, may I inquire, how is this consistent with the known exponential lower bounds on TC$_2^0$ and the separation of depth 3 from depth 2 threshold circuits, as reported in the complexity zoo? Am I missing something? $\endgroup$ – Dilworth Jul 24 '13 at 13:35
  • 1
    $\begingroup$ @Dilworth, I think that is because it is defined using Majority not Threshold. $\endgroup$ – Kaveh Jul 24 '13 at 13:38
  • $\begingroup$ Hmm.. what do you mean precisely? Is this related to the note made by Kristoffer about "unbounded weights"? $\endgroup$ – Dilworth Jul 24 '13 at 13:43
12
$\begingroup$

If I am not making a mistake, it seems that proving that the $\mathsf{TC^0_d}$ hierarchy does not collapse is at least as difficult as separating $\mathsf{NC^1}$ from $\mathsf{TC^0}$:

Let's denote the Boolean Formula Evaluation problem by $BFE$. $BFE$ is complete for $\mathsf{NC^1}$ under $\mathsf{AC^0}$ reductions.

By Manindra Agrawal, Eric Allender, and Steven Rudich, "Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem", 1999, $BFE$ is complete for $\mathsf{NC^1}$ under $\mathsf{AC^0_2}$ reductions.

Assume $\mathsf{NC^1}=\mathsf{TC^0}$. Then $BFE \in \mathsf{TC^0_d}$ for some $d$. Therefore $\mathsf{NC^1} \subseteq \mathsf{TC^0_{d+2}}$. Which means that $\mathsf{TC^0} \subseteq \mathsf{TC^0_{d+2}}$.

So for all $d$ we have

$\mathsf{TC^0} \not\subseteq \mathsf{TC^0_d}$ implies $\mathsf{NC^1} \not\subseteq \mathsf{TC^0_{d+2}}$ and $BFE \notin \mathsf{TC^0_d}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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