En álgebra booleana , una función de paridad es una función booleana cuyo valor es 1 si y solo si el vector de entrada tiene un número impar de unos. La función de paridad de dos entradas también se conoce como función XOR .
La función de paridad es notable por su papel en la investigación teórica de la complejidad del circuito de las funciones booleanas.
La salida de la función de paridad es el bit de paridad .
Definición
La -la función de paridad variable es la función booleana con la propiedad que si y solo si el número de unos en el vectores impar. En otras palabras, se define de la siguiente manera:
dónde denota exclusivo o .
Propiedades
La paridad solo depende del número de unos y, por lo tanto, es una función booleana simétrica .
La función de paridad n- variable y su negación son las únicas funciones booleanas para las cuales todas las formas normales disyuntivas tienen el número máximo de 2 n - 1 monomios de longitud n y todas las formas normales conjuntivas tienen el número máximo de 2 n - 1 cláusulas de longitud n . [1]
Complejidad computacional
Uno de los primeros trabajos sobre complejidad computacional fue el encuadernado de Bella Subbotovskaya en 1961, que muestra que el tamaño de una fórmula booleana que computa la paridad debe ser al menos. Este trabajo utiliza el método de restricciones aleatorias. Este exponente de se ha incrementado a través de un análisis cuidadoso para por Paterson y Zwick (1993) y luego apor Håstad (1998). [2]
A principios de la década de 1980, Merrick Furst , James Saxe y Michael Sipser [3] e independientemente Miklós Ajtai [4] establecieron límites inferiores superpolinomiales en el tamaño de los circuitos booleanos de profundidad constante para la función de paridad, es decir, mostraron que el polinomio- Los circuitos de profundidad constante de tamaño no pueden calcular la función de paridad. También se establecieron resultados similares para las funciones de mayoría, multiplicación y cierre transitivo, por reducción de la función de paridad. [3]
Håstad (1987) estableció límites inferiores exponenciales estrictos en el tamaño de los circuitos booleanos de profundidad constante para la función de paridad. El Switching Lemma de Håstad es la herramienta técnica clave utilizada para estos límites inferiores y Johan Håstad recibió el Premio Gödel por este trabajo en 1994. El resultado preciso es que los circuitos de profundidad k con puertas Y, O y NO requieren tamaño.para calcular la función de paridad. Esto es asintóticamente casi óptimo ya que hay circuitos de profundidad k que calculan la paridad que tienen un tamaño.
Versión infinita
Una función de paridad infinita es una función mapeando cada cadena binaria infinita a 0 o 1, teniendo la siguiente propiedad: si y son cadenas binarias infinitas que difieren solo en un número finito de coordenadas, entonces si y solo si y difieren en un número par de coordenadas.
Suponiendo el axioma de elección, se puede demostrar fácilmente que existen funciones de paridad y que existen muchos de ellos - tantos como el número de todas las funciones de a . Es suficiente tomar un representante por clase de relación de equivalencia. definido como sigue: Si y difieren en un número finito de coordenadas. Teniendo tales representantes, podemos asignarlos a todos a 0; el resto de los valores se deducen sin ambigüedades.
Las funciones de paridad infinita se utilizan a menudo en la informática teórica y la teoría de conjuntos debido a su definición simple y, por otro lado, a su complejidad descriptiva. Por ejemplo, se puede mostrar que una imagen inversaes un conjunto que no es de Borel .
Ver también
- Función de Walsh , equivalente continuo
Temas relacionados
La salida de la función
Propiedad estadística para entradas independientes:
Referencias
- ^ Ingo Wegener , Randall J. Pruim, Teoría de la complejidad , 2005, ISBN 3-540-21045-8 , p. 260
- ^ Jukna, Stasys (6 de enero de 2012). Complejidad de funciones booleanas: avances y fronteras . Springer Science & Business Media. págs. 167-173. ISBN 978-3642245084.
- ^ a b Merrick Furst, James Saxe y Michael Sipser, "Paridad, circuitos y la jerarquía de tiempo polinomial", Annu. Intl. Symp. Encontrado Computer Sci., 1981, Teoría de los sistemas informáticos , vol. 17, no. 1, 1984, págs. 13-27, doi : 10.1007 / BF01744431
- ^ Miklós Ajtai, "-Formulae on Finite Structures ", Annals of Pure and Applied Logic , 24 (1983) 1-48.
- Håstad, Johan (1987), Limitaciones computacionales de circuitos de pequeña profundidad (PDF) , Ph.D. tesis, Instituto de Tecnología de Massachusetts.