Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR13-131 | 30th November 2013 16:18

Collapsing Exact Arithmetic Hierarchies

RSS-Feed




Revision #1
Authors: Nikhil Balaji, Samir Datta
Accepted on: 30th November 2013 16:18
Downloads: 534
Keywords: 


Abstract:

We provide a uniform framework for proving the collapse of the hierarchy, $NC^1(\mathcal{C})$
for an exact arithmetic class $\mathcal{C}$ of polynomial degree. These hierarchies collapses all the way down to the third level of the ${AC}^0$-hierarchy, ${AC^0_3}(\mathcal{C})$. Our main collapsing exhibits are the classes \[\mathcal{C} \in \{{C}_={NC^1}, {C}_={L}, {C}_={SAC^1}, {C}_={P}\}.\]
${NC^1}({C}_={L})$ and ${NC^1}({C}_={P})$ are already known to collapse \cite{ABO,Ogihara95,Ogiwara94}.

We reiterate that our contribution is a framework that works for \emph{all} these hierarchies.
Our proof generalizes a proof from \cite{DMRTV} where it is used to prove the
collapse of the ${AC}^0({C}_={NC^1})$ hierarchy. It is essentially based on a polynomial
degree characterization of each of the base classes.



Changes to previous version:

Fixed typos, reformatted images.


Paper:

TR13-131 | 17th September 2013 14:24

Collapsing Exact Arithmetic Hierarchies





TR13-131
Authors: Nikhil Balaji, Samir Datta
Publication: 18th September 2013 22:02
Downloads: 1146
Keywords: 


Abstract:

We provide a uniform framework for proving the collapse of the hierarchy, $NC^1(\mathcal{C})$
for an exact arithmetic class $\mathcal{C}$ of polynomial degree. These hierarchies collapses all the way down to the third level of the ${AC}^0$-hierarchy, ${AC^0_3}(\mathcal{C})$. Our main collapsing exhibits are the classes \[\mathcal{C} \in \{{C}_={NC^1}, {C}_={L}, {C}_={SAC^1}, {C}_={P}\}.\]
${NC^1}({C}_={L})$ and ${NC^1}({C}_={P})$ are already known to collapse \cite{ABO,Ogihara95,Ogiwara94}.

We reiterate that our contribution is a framework that works for \emph{all} these hierarchies.
Our proof generalizes a proof from \cite{DMRTV} where it is used to prove the
collapse of the ${AC}^0({C}_={NC^1})$ hierarchy. It is essentially based on a polynomial
degree characterization of each of the base classes.



ISSN 1433-8092 | Imprint