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$
8
  • 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$ 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$ 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$ 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
15
$\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$
5
  • $\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.