Extensional Uniformity for Boolean Circuits

Simple item page
dc.creatorMcKenzie, Pierre
dc.creatorThomas, Michael
dc.creatorVollmer, Heribert
dc.date2008-05-27
dc.date2008-05-28
dc.date.accessioned2026-07-07T12:19:14Z
dc.date.available2026-07-07T12:19:14Z
dc.descriptionImposing an extensional uniformity condition on a non-uniform circuit complexity class C means simply intersecting C with a uniform class 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 C. We say that (C,L) has the "Uniformity Duality Property" if the extensionally uniform class C \cap L can be captured intensionally by means of adding so-called "L-numerical predicates" to the first-order descriptive complexity apparatus describing the connection language of the circuit family defining C. This paper exhibits positive instances and negative instances of the Uniformity Duality Property.
dc.identifierhttps://arxiv.org/abs/0805.4072
dc.identifierhttp://arxiv.org/abs/0805.4072
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/212683
dc.subjectLogic in Computer Science
dc.subjectComputational Complexity
dc.titleExtensional Uniformity for Boolean Circuits
dc.typetext

Files

Collections

arXiv