Función de paridad - Parity function

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 función de paridad variable es la función booleana con la propiedad de que si y solo si el número de unos en el vector es impar. En otras palabras, se define de la siguiente manera: ${\ Displaystyle n}$ ${\ Displaystyle f: \ {0,1 \} ^ {n} \ to \ {0,1 \}}$${\ Displaystyle f (x) = 1}$ ${\ Displaystyle x \ in \ {0,1 \} ^ {n}}$${\ Displaystyle f}$

${\ Displaystyle f (x) = x_ {1} \ oplus x_ {2} \ oplus \ dots \ oplus x_ {n}}$

donde denota exclusivo o . ${\ Displaystyle \ oplus}$

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 ny todas las formas normales conjuntivas tienen el número máximo de 2 ^{n  - 1} cláusulas de longitud n .    

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 debe ser al menos de paridad computacional . Este trabajo utiliza el método de restricciones aleatorias. Este exponente de ha sido aumentado a través de un análisis cuidadoso de Paterson y Zwick (1993) y luego de Håstad (1998). ${\ Displaystyle O (n ^ {3/2})}$${\ Displaystyle 3/2}$${\ Displaystyle 1,63}$${\ Displaystyle 2}$

A principios de la década de 1980, Merrick Furst , James Saxe y Michael Sipser e independientemente Miklós Ajtai 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 circuitos de profundidad constante de tamaño polinómico 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.

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 compuertas AND, OR y NOT requieren un 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 que tienen tamaño . ${\ Displaystyle \ exp (\ Omega (n ^ {\ frac {1} {k-1}}))}$${\ Displaystyle \ exp (O (n ^ {\ frac {1} {k-1}}) t)}$

Versión infinita

Una función de paridad infinita es una función que asigna cada cadena binaria infinita a 0 o 1, que 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. ${\ Displaystyle f \ colon \ {0,1 \} ^ {\ omega} \ to \ {0,1 \}}$${\ Displaystyle w}$${\ Displaystyle v}$${\ Displaystyle f (w) = f (v)}$${\ Displaystyle w}$${\ Displaystyle v}$

Suponiendo el axioma de elección, se puede probar fácilmente que existen funciones de paridad y que hay muchas de ellas, tantas como el número de todas las funciones desde hasta . Es suficiente tomar un representante por clase de equivalencia de relación definida como sigue: si y difieren en un número finito de coordenadas. Teniendo tales representantes, podemos asignarlos a todos a 0; el resto de valores se deducen sin ambigüedades. ${\ Displaystyle 2 ^ {\ mathfrak {c}}}$${\ Displaystyle \ {0,1 \} ^ {\ omega}}$${\ Displaystyle \ {0,1 \}}$${\ Displaystyle \ approx}$${\ Displaystyle w \ approx v}$${\ Displaystyle w}$${\ Displaystyle v}$${\ Displaystyle f}$

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 inversa es un conjunto que no es Borel . ${\ displaystyle f ^ {- 1} [0]}$

Ver también

• Función de Walsh , un equivalente continuo
• Bit de paridad , la salida de la función
• Lema de acumulación , una propiedad estadística para entradas independientes
• Conmutación de múltiples vías , una implementación física que se usa a menudo para controlar la iluminación

Temas relacionados:

• Error de corrección
• Detección de errores

Referencias