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$

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .