Extensional Uniformity for Boolean Circuits

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

Imposing 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.

Keywords

Logic in Computer Science, Computational Complexity

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/212683

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0805.4072
 http://arxiv.org/abs/0805.4072

Collections

arXiv