Skip to main content
Theoretical Computer Science

Return to Question

Post Closed as "Not suitable for this site" by Niel de Beaudrap, Kaveh, R B, Emil Jeřábek, Kristoffer Arnsfelt Hansen
deleted 1 character in body
Source Link
Kaveh
Kaveh
  • 21.9k
  • 8
  • 84
  • 185

According to wiki we know that $$\mathsf{ACC^0\subseteq TC^0\subseteq NC^1\subseteq L\subseteq P\subseteq NP\subsetneq NEXPTIME}.$$\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?

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?

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?

added 224 characters in body
Source Link
Turbo
Turbo
  • 13.3k
  • 1
  • 20
  • 71

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?

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)?

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?

added 533 characters in body
Source Link
Turbo
Turbo
  • 13.3k
  • 1
  • 20
  • 71

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\subseteq TC^0\subseteq NC^1\subseteq L\subseteq P\subseteq NP\subsetneq NEXPTIME}$$ the last inequality from Time hierarchy theorem$\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)?

According to wiki we know that $$\mathsf{ACC^0\subseteq TC^0\subseteq NC^1\subseteq L\subseteq P\subseteq NP\subsetneq NEXPTIME}$$ the last inequality from Time hierarchy theorem (http://en.wikipedia.org/wiki/NEXPTIME).

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)?

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)?

added 55 characters in body
Source Link
Turbo
Turbo
  • 13.3k
  • 1
  • 20
  • 71
Source Link
Turbo
Turbo
  • 13.3k
  • 1
  • 20
  • 71