Topology Inside NC¹
Eric Allender, Samir K. Datta, Sambuddha Roy · 2005
We show that ACC/sup 0/ is precisely what can be computed with constant-width circuits of polynomial size and polylogarithmic genus. This extends a characterization given by Hansen, showing that planar constant-width circuits also characterize ACC/sup 0/. Thus polylogarithmic genus provides no additional computational power in this model. We consider other generalizations of planarity, including crossing number and thickness. We show that thickness two already suffices to capture all of NC/sup 1/.