Revision #1 Authors: Nikhil Balaji, Samir Datta

Accepted on: 30th November 2013 16:18

Downloads: 1267

Keywords:

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.

Fixed typos, reformatted images.

TR13-131 Authors: Nikhil Balaji, Samir Datta

Publication: 18th September 2013 22:02

Downloads: 2909

Keywords:

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.