Función de paridad

En álgebra de Boole , una función de paridad es una función booleana cuyo valor es uno 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 funciones booleanas.

La salida de la función de paridad es el bit de paridad .

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: ${\estilo de visualización n}$ ${\displaystyle f:\{0,1\}^{n}\to \{0,1\}}$${\displaystyle f(x)=1}$ ${\displaystyle x\en \{0,1\}^{n}}$${\estilo de visualización f}$

${\displaystyle f(x)=x_{1}\omás x_{2}\omás \puntos \omás x_{n}}$

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

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 variables 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]   

Uno de los primeros trabajos sobre complejidad computacional fue el de 1961 de Bella Subbotovskaya, que mostraba que el tamaño de una fórmula booleana para calcular la paridad debe ser al menos . Este trabajo utiliza el método de restricciones aleatorias. Este exponente de se ha incrementado mediante un análisis cuidadoso hasta por Paterson y Zwick (1993) y luego hasta por Håstad (1998). ^[2]${\displaystyle O(n^{3/2})}$${\estilo de visualización 3/2}$${\estilo de visualización 1.63}$${\estilo de visualización 2}$

A principios de los años 1980, Merrick Furst, James Saxe y Michael Sipser ^[3] e independientemente Miklós Ajtai ^{[4] establecieron} límites inferiores superpolinómicos para el tamaño de 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 clausura transitiva, mediante reducción a partir 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 función de paridad. Esto es asintóticamente casi óptimo ya que hay circuitos de profundidad k que calculan paridad que tienen tamaño . ${\displaystyle \exp(\Omega (n^{\frac {1}{k-1}}))}$${\displaystyle \exp(O(n^{\frac {1}{k-1}})t)}$

Una función de paridad infinita es una función que asigna cada cadena binaria infinita a 0 o 1 y 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\}}$${\estilo de visualización w}$${\estilo de visualización v}$${\displaystyle f(w)=f(v)}$${\estilo de visualización w}$${\estilo de visualización v}$

Suponiendo el axioma de elección, se puede demostrar 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 de la siguiente manera: si y difieren en un número finito de coordenadas. Teniendo tales representantes, podemos mapear todos ellos a ; el resto de valores se deducen inequívocamente. ${\displaystyle 2^{2^{\aleph _ {0}}}}$${\displaystyle \{0,1\}^{\omega }}$${\estilo de visualización \{0,1\}}$${\displaystyle \aprox }$${\displaystyle w\aprox v}$${\estilo de visualización w}$${\estilo de visualización v}$${\estilo de visualización 0}$${\estilo de visualización f}$

Otra construcción de una función de paridad infinita se puede realizar utilizando un ultrafiltro no principal en . La existencia de ultrafiltros no principales en se sigue del axioma de elección (y es estrictamente más débil que él). Para cualquier consideramos el conjunto . La función de paridad infinita se define mapeando a si y solo si es un elemento del ultrafiltro. ${\estilo de visualización U}$${\estilo de visualización \omega}$${\estilo de visualización \omega}$${\displaystyle w:\omega \to \{0,1\}}$${\displaystyle A_{w}=\{n\in \omega \mid \{k\leq n\mid w(k)=0\}{\text{ es par}}\}}$${\estilo de visualización f}$${\estilo de visualización w}$${\estilo de visualización 0}$$Estilo de visualización A_ {w}}$

Es necesario suponer al menos cierta cantidad de elección para demostrar que existen funciones de paridad infinitas. Si es una función de paridad infinita y consideramos la imagen inversa como un subconjunto del espacio de Cantor , entonces es un conjunto no medible y no tiene la propiedad de Baire . Sin el axioma de elección, es consistente (en relación con ZF ) que todos los subconjuntos del espacio de Cantor sean mesurables y tengan la propiedad de Baire y, por lo tanto, que no exista ninguna función de paridad infinita; esto se cumple en el modelo de Solovay , por ejemplo. ${\estilo de visualización f}$$estilo de visualización f^{-1}[0]}$ ${\displaystyle \{0,1\}^{\omega }}$$estilo de visualización f^{-1}[0]}$

• Función de Walsh , un equivalente continuo
• Bit de paridad , la salida de la función
• Lema de apilamiento , una propiedad estadística para entradas independientes
• Conmutación multidireccional , una implementación física que se utiliza a menudo para controlar la iluminación.

Temas relacionados:

• Corrección de errores
• Detección de errores