Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

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

#### Collapsing Exact Arithmetic Hierarchies

Revision #1
Authors: Nikhil Balaji, Samir Datta
Accepted on: 30th November 2013 16:18
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
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