-2
$\begingroup$

According to wiki we know that $\mathsf{ACC^0\subseteq TC^0\subseteq NC^1\subseteq L\subseteq P\subseteq NP\subsetneq NEXPTIME}.$

Class $\mathsf{ACC^0}$ is included in $\mathsf{TC^0}$ is in http://en.wikipedia.org/wiki/ACC0#Computational_power.

Class $\mathsf{TC^0}$ is included in $\mathsf{NC^1}$ is in https://en.wikipedia.org/wiki/TC0.

Class $\mathsf{NC^1}$ is included in $\mathsf{L}$ which is included in $\mathsf{P}$ is in https://en.wikipedia.org/wiki/NC_(complexity)#The_NC_hierarchy.

Class $\mathsf{P}$ is included in $\mathsf{NP}$ is in https://en.wikipedia.org/wiki/P_(complexity)#Relationships_to_other_classes.

Class $\mathsf{NP\subsetneq NEXPTIME}$ is in http://en.wikipedia.org/wiki/NEXPTIME from time hierarchy theorem.

So does it mean, we already know $\mathsf{ACC^0\subsetneq NEXPTIME}$ even before Ryan Williams' breakthrough(http://en.wikipedia.org/wiki/ACC0#Computational_power)?

It seems that from discussion below(with Niel de Beaudrap, Ricky Demer) $\mathsf{ACC^0\subseteq TC^0}$ mentioned in http://en.wikipedia.org/wiki/ACC0#Computational_power is false. Could someone please clarify?

Improve this question
$\endgroup$
23
  • 1
    $\begingroup$ While Wikipedia can be a good place to point people to for basic reference, you should also be careful of citing class containments as being "from/according to Wiki", because that's not where the results are actually coming from. (For instance, it's not great to point to Wikipedia for $\mathsf{ACC^0 \subseteq TC^0}$, because the Wikipedia page doesn't say why this result should hold nor give a reference for this fact.) $\endgroup$
    – Niel de Beaudrap
    Commented Apr 27, 2015 at 2:31
  • 1
    $\begingroup$ You might want to search for "nonuniform circuits" or "nonuniformity circuits", but Arora+Barak's Computational Complexity: A Modern Approach (chapter 6) is one place to learn a little about the 'uniformity' distinction. $\endgroup$
    – Niel de Beaudrap
    Commented Apr 27, 2015 at 2:41
  • 2
    $\begingroup$ Results for circuit classes are almost always for uniform circuits of some sort, e.g. logspace-uniform circuits (whose specification can be computed by a logspace-bounded deterministic Turing machine). However, when in doubt you should consult the original sources to determine which uniformity condition is being used. In this case, William's result is being summarised sloppily by Wikipedia, but simply consulting the title of the reference clarifies that it is a result for non-uniform circuits. $\endgroup$
    – Niel de Beaudrap
    Commented Apr 27, 2015 at 3:03
  • 2
    $\begingroup$ For uniform classes it is known since 1996 that TC0 is strictly contained in PP (i.e. TC0 does not contain PP). Ryan's result is that even with nonuniformity ACC0 doesn't contain NExpTime. $\endgroup$
    – Kaveh
    Commented Apr 27, 2015 at 4:51
  • 4
    $\begingroup$ ps: if you are seriously interested in topic to the extend that you keep posting questions on it then you should at least read a good textbook on that topic and I feels like you haven't done so. $\endgroup$
    – Kaveh
    Commented Apr 27, 2015 at 4:51

1 Answer 1

Reset to default
4
$\begingroup$

NC1 $\: = \:$ DLOGTIME-uniform NC1 $\: \subseteq \:$ logspace-uniform NC1 $\: \subseteq \:$ L
and $\;\;\;\;$ non-uniform NC1 $\: \not\subseteq \:$ L $\;\;\;\;$ .

Ryan Williams showed that $\;\;\;$ NTIME[$2^{\hspace{.02 in}n}$] $\: \not\subseteq \:$ non-uniform ACC0 $\;\;\;$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ In this context, what is the result that is actually inferred from wiki? $\endgroup$
    – Turbo
    Commented Apr 27, 2015 at 2:14
  • $\begingroup$ I'm not inferring any of those results from wiki. $\;$ $\endgroup$
    – user6973
    Commented Apr 27, 2015 at 2:15
  • $\begingroup$ I mean wiki states $ACC0$ is contained in $TC0$ which is in $NC1$ so on.. is it talking about this in uniform context? $\endgroup$
    – Turbo
    Commented Apr 27, 2015 at 2:18
  • $\begingroup$ Ok certainly I am missing difference between uniform and non-uniform circuits. $\endgroup$
    – Turbo
    Commented Apr 27, 2015 at 2:21
  • $\begingroup$ TC0 $\subseteq$ NC1 $\:$ holds both in the non-uniform context and for any reasonable uniformity condition. I don't know anything about the $\:$ ACC0 $\subseteq$ TC0 $\:$ containment. $\;\;\;\;\;\;$ $\endgroup$
    – user6973
    Commented Apr 27, 2015 at 2:34

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