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

<p>Class $\mathsf{ACC^0}$ is included in $\mathsf{TC^0}$ is in <a href="http://en.wikipedia.org/wiki/ACC0#Computational_power" rel="nofollow">http://en.wikipedia.org/wiki/ACC0#Computational_power</a>.</p>

<p>Class $\mathsf{TC^0}$ is included in $\mathsf{NC^1}$ is in <a href="https://en.wikipedia.org/wiki/TC0" rel="nofollow">https://en.wikipedia.org/wiki/TC0</a>.</p>

<p>Class $\mathsf{NC^1}$ is included in $\mathsf{L}$ which is included in $\mathsf{P}$ is in 
<a href="https://en.wikipedia.org/wiki/NC_(complexity)#The_NC_hierarchy" rel="nofollow">https://en.wikipedia.org/wiki/NC_(complexity)#The_NC_hierarchy</a>.</p>

<p>Class $\mathsf{P}$ is included in $\mathsf{NP}$ is in <a href="https://en.wikipedia.org/wiki/P_(complexity)#Relationships_to_other_classes" rel="nofollow">https://en.wikipedia.org/wiki/P_(complexity)#Relationships_to_other_classes</a>.</p>

<p>Class $\mathsf{NP\subsetneq NEXPTIME}$ is in <a href="http://en.wikipedia.org/wiki/NEXPTIME" rel="nofollow">http://en.wikipedia.org/wiki/NEXPTIME</a> from time hierarchy theorem.</p>

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

<hr>

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

CC BY-SA 3.0
2015-04-27T02:31:51.247Z
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.)
Niel de Beaudrap
CC BY-SA 3.0
2015-04-27T02:34:09.143Z
sorry what is a good reference to understand the hierarchy and uniformness/non-uniformness distinction that Ricky Demer is posting. Where could I find result on what Ricky Demer has posted?
Turbo
CC BY-SA 3.0
2015-04-27T02:35:17.897Z
Actually it states "It is conjectured that ACC0 is unable to compute the majority function of its inputs (i.e. the inclusion in TC0 is strict)"
Turbo
CC BY-SA 3.0
2015-04-27T02:41:37.953Z
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.
Niel de Beaudrap
CC BY-SA 3.0
2015-04-27T02:46:38.510Z
So wiki results on $ACC^0$ are only for uniform circuits, right?
Turbo
CC BY-SA 3.0
2015-04-27T03:03:51.123Z
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.
Niel de Beaudrap
CC BY-SA 3.0
2015-04-27T03:08:48.267Z
Ok that clarifies things a bit. Wiki is correct on that they give results on uniform classes. Ryan's work is on non-uniform classes which are more powerful than uniform classes. So Ryan's breakthrough is not included in wiki summary except for that one line sloppy statement which mentions Ryan's breakthrough. In summary $uniformACC0\subseteq uniformTC0$ is correct. But non-uniform ACC0 could be much more powerful which is what Ryan's result tries. Correct?
Turbo
CC BY-SA 3.0
2015-04-27T03:22:25.293Z
ACC^0 is contained in TC^0 regardless of uniformity/non-uniformity -- that just follows from the fact that you can simulate unbounded fan-in AND, OR and MOD_m by unbounded fan-in MAJORITY gates in constant depth. However, only when you impose uniformity, we know the containment $ACC^0 \subseteq NP$ or $TC^0 \subseteq NP$ which allows one to invoke Hierarchy theorems.
Nikhil
CC BY-SA 3.0
2015-04-27T03:24:55.650Z
@Nikhil Then what is Ryan's result about (since we already know $\mathsf{NP\subsetneq NEXP}$, so your statement $\mathsf{\implies ACC^0\subsetneq NEXP}$?
Turbo
CC BY-SA 3.0
2015-04-27T03:28:49.663Z
@RickyDemer Nikhil states regardless of uniformity or not $\mathsf{ACC^0\subseteq TC^0\subseteq NP\subsetneq NEXP}$ holds.
Turbo
CC BY-SA 3.0
2015-04-27T03:31:23.730Z
ACC^0 is contained in TC^0 regardless of uniformity/non-uniformity.
Turbo
CC BY-SA 3.0
2015-04-27T03:32:05.500Z
oic ok... there are two things going on. non-uniform TC^0 could contain NEXP. Only uniform TC^0  does not contain NEXP.
Turbo
CC BY-SA 3.0
2015-04-27T03:44:12.143Z
So moral of story is uniform circuits are like turing machines, non-uniformity is slightly more powerful, we get a turing machine for every input length.
Turbo
CC BY-SA 3.0
2015-04-27T04:51:28.527Z
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.
Kaveh
CC BY-SA 3.0
2015-04-27T04:51:42.053Z
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.
Kaveh
CC BY-SA 3.0
2015-04-27T04:52:54.267Z
@Kaveh what is a good text for circuit complexity?
Turbo
CC BY-SA 3.0
2015-04-27T04:55:18.073Z
Arora and Barak's book is a commonly used textbook.
Kaveh
CC BY-SA 3.0
2018-01-04T23:46:20.797Z
@Turbo I recommend reading https://en.wikipedia.org/wiki/Advice_(complexity) . It clarifies the power of non-uniformity.
Albert Hendriks
CC BY-SA 3.0
2018-01-05T04:22:13.063Z
@AlbertHendriks It is an old query. I moved beyond that stage.
Turbo
CC BY-SA 3.0
2018-01-05T11:50:08.493Z
I'm in that stage now.
Albert Hendriks
<circuit-complexity><big-picture>
A trivial question on hierarchy
Turbo
# A trivial question on hierarchy

(Asked by: username_0 on 2015-04-27)

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?

**Tags:** circuit-complexity, big-picture
> **Comments:**
> **username_1**: 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.)  
> **username_0**: sorry what is a good reference to understand the hierarchy and uniformness/non-uniformness distinction that Ricky Demer is posting. Where could I find result on what Ricky Demer has posted?  
> **username_0**: Actually it states "It is conjectured that ACC0 is unable to compute the majority function of its inputs (i.e. the inclusion in TC0 is strict)"  
> **username_1**: 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.  
> **username_0**: So wiki results on $ACC^0$ are only for uniform circuits, right?  
> **username_1**: 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.  
> **username_0**: Ok that clarifies things a bit. Wiki is correct on that they give results on uniform classes. Ryan's work is on non-uniform classes which are more powerful than uniform classes. So Ryan's breakthrough is not included in wiki summary except for that one line sloppy statement which mentions Ryan's breakthrough. In summary $uniformACC0\subseteq uniformTC0$ is correct. But non-uniform ACC0 could be much more powerful which is what Ryan's result tries. Correct?  
> **username_2**: ACC^0 is contained in TC^0 regardless of uniformity/non-uniformity -- that just follows from the fact that you can simulate unbounded fan-in AND, OR and MOD_m by unbounded fan-in MAJORITY gates in constant depth. However, only when you impose uniformity, we know the containment $ACC^0 \subseteq NP$ or $TC^0 \subseteq NP$ which allows one to invoke Hierarchy theorems.  
> **username_0**: @Nikhil Then what is Ryan's result about (since we already know $\mathsf{NP\subsetneq NEXP}$, so your statement $\mathsf{\implies ACC^0\subsetneq NEXP}$?  
> **username_0**: @RickyDemer Nikhil states regardless of uniformity or not $\mathsf{ACC^0\subseteq TC^0\subseteq NP\subsetneq NEXP}$ holds.  
> **username_0**: ACC^0 is contained in TC^0 regardless of uniformity/non-uniformity.  
> **username_0**: oic ok... there are two things going on. non-uniform TC^0 could contain NEXP. Only uniform TC^0  does not contain NEXP.  
> **username_0**: So moral of story is uniform circuits are like turing machines, non-uniformity is slightly more powerful, we get a turing machine for every input length.  
> **username_3**: 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.  
> **username_3**: 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.  
> **username_0**: @Kaveh what is a good text for circuit complexity?  
> **username_3**: Arora and Barak's book is a commonly used textbook.  
> **username_4**: @Turbo I recommend reading https://en.wikipedia.org/wiki/Advice_(complexity) . It clarifies the power of non-uniformity.  
> **username_0**: @AlbertHendriks It is an old query. I moved beyond that stage.  
> **username_4**: I'm in that stage now.  

---

## 0 answers

