Extensional Uniformity for Boolean Circuits

Abstract Imposing an extensional uniformity condition on a non-uniform circuit complexity class \(\mathcal{C}\) means simply intersecting \(\mathcal{C}\) with a uniform class \(\mathcal{L}\). By contrast, the usual intensional uniformity conditions require that a resource-bounded machine be able to exhibit the circuits in the circuit family defining \(\mathcal{C}\). We say that \((\mathcal{C}, \mathcal{L})\) has the Uniformity Duality Property if the extensionally uniform class \(\mathcal{C}\cap\mathcal{L}\) can be captured intensionally by means of adding so-called \(\mathcal{L}\) -numerical predicates to the first-order descriptive complexity apparatus describing the connection language of the circuit family defining \(\mathcal{C}\). This paper exhibits positive instances and negative instances of the Uniformity Duality Property.

Authors

• Pierre McKenzie
• Michael Thomas 0001
• Heribert Vollmer

Keywords

No keywords are indexed for this paper.