Nada

Circuitos Booleanos

Actualmente existe una variedad de modelos abstractos para computación paralela. Los circuitos booleanos constituyen uno de tales modelos. La complejidad de circuitosbooleanos es de interés tanto en lo práctico como en lo teórico, y por ello mostraremos cómo en nuestro problema ellos constituyen un modelo apropiado para su estudio.
Los circuitos booleanos tienencomo característica propia, a diferencia de otros modelos computacionales, que su entrada es de longitud fija por lo que para cada tamaño de entrada se debe construir el circuito booleanocorrespondiente. Esto conduce a la generación de una familia infinita de circuitos booleanos, uno por cada posible longitud de la entrada, y aún más, la estructura de los mismos puede llegar a variar según eltamaño de entrada dependiendo de la función que computen. Por ello, los circuitos booleanos son referidos como un modelo de computación no uniforme.
Si miramos una máquina de Turing o un lenguaje deprogramación, ellos pueden describir un algoritmo que resuelva un problema para cualquier entrada dada, independiente de la longitud de la misma. Tales modelos son referidos como modelos Uniformes decomputación.
En nuestro caso, generamos una subfamilia finita de circuitos booleanos, dado que tanto la fórmula como la cardinalidad del dominio son considerados la entrada para el algoritmo quegenera los mismos, por lo que se preserva la propiedad uniformidad.
Nuestros circuitos booleanos pertenecen a la clase NC, la cual es de fundamental importancia en la teoría de paralelismo,porque ella captura los problemas para los cuales se pueden describir algoritmos paralelos utilizando una cantidad factible de recursos de computación.
Se define
• Una función booleana m-aria comof( {0,1}m ({0,1}, para algún m ((.
• Una familia de funciones booleanas como una secuencia f= (fn)n(( donde fn es una función booleana n-aria.
• Una base como un conjunto finito de funciones...