En álgebra booleana , una función de paridad es una función booleana cuyo valor es uno si y sólo 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 destaca por su papel en la investigación teórica de la complejidad del circuito de funciones booleanas.
La salida de la función de paridad es el bit de paridad .
La función de paridad de variable es la función booleana con la propiedad de que si y sólo si el número de unos en el vector es impar. En otras palabras, se define de la siguiente manera:
donde denota exclusivo o .
La paridad sólo depende del número de unos y por tanto es una función booleana simétrica .
La función de paridad de 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]
Algunos de los primeros trabajos sobre complejidad computacional fueron los de Bella Subbotovskaya de 1961 , que muestran que el tamaño de una fórmula booleana que calcula la paridad debe ser al menos . Este trabajo utiliza el método de restricciones aleatorias. Este exponente se ha incrementado mediante un análisis cuidadoso de Paterson y Zwick ( 1993) y luego de 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, demostraron que los polinomios- Los circuitos de tamaño constante y profundidad 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 para el tamaño de los circuitos booleanos de profundidad constante para la función de paridad. El lema de conmutación 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 AND, OR y NOT requieren tamaño para calcular la paridad. función. Esto es asintóticamente casi óptimo ya que hay circuitos de profundidad k que calculan la paridad y tienen un tamaño .
Una función de paridad infinita es una función que asigna cada cadena binaria infinita a 0 o 1, y tiene 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 hay muchas, tantas como el número de todas las funciones desde hasta . Basta tomar un representante por clase de equivalencia de relación definida de la siguiente manera: si y difieren en un número finito de coordenadas. Teniendo tales representantes, podemos asignarlos todos a 0; el resto de valores se deducen de forma inequívoca.
Las funciones de paridad infinita se utilizan a menudo en informática teórica y teoría de conjuntos debido a su definición simple y, por otro lado, a su complejidad descriptiva. Por ejemplo, se puede demostrar que una imagen inversa es un conjunto que no es de Borel .
Temas relacionados: