ECCC-Report TR13-131https://eccc.weizmann.ac.il/report/2013/131Comments and Revisions published for TR13-131en-usSat, 30 Nov 2013 16:18:10 +0200
Revision 1
| Collapsing Exact Arithmetic Hierarchies |
Nikhil Balaji,
Samir Datta
https://eccc.weizmann.ac.il/report/2013/131#revision1We 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.Sat, 30 Nov 2013 16:18:10 +0200https://eccc.weizmann.ac.il/report/2013/131#revision1
Paper TR13-131
| Collapsing Exact Arithmetic Hierarchies |
Nikhil Balaji,
Samir Datta
https://eccc.weizmann.ac.il/report/2013/131We 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.Wed, 18 Sep 2013 22:02:39 +0300https://eccc.weizmann.ac.il/report/2013/131