Función de paridad

En álgebra booleana , una función de paridad es una función booleana cuyo valor es uno si y solo si el vector de entrada contiene 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 de los circuitos de funciones booleanas.

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

El${\displaystyle n}$La función de paridad variable es la función booleana.${\displaystyle f:\{0,1\}^{n}\to \{0,1\}}$con la propiedad que${\displaystyle f(x)=1}$si y solo si el número de unos en el vector${\displaystyle x\in \{0,1\}^{n}}$es extraño. En otras palabras,${\displaystyle f}$se define de la siguiente manera:

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

dónde${\displaystyle \oplus }$denota exclusivo o .

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

Algunos de los primeros trabajos en complejidad computacional fueron los de Bella Subbotovskaya en 1961 , que demostraron que el tamaño de una fórmula booleana que calcula la paridad debe ser al menos${\displaystyle \Omega (n^{3/2})}$Este trabajo utiliza el método de restricciones aleatorias. Este exponente de${\displaystyle 3/2}$se ha incrementado mediante un análisis cuidadoso para${\displaystyle 1.63}$por Paterson y Zwick (1993) y luego a${\displaystyle 2}$por 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 cotas inferiores superpolinómicas para 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. Resultados similares también se establecieron para las funciones de cierre de mayoría, multiplicación y transitivo , mediante reducción a partir de la función de paridad. ^{[ 3 ]}

Håstad (1987) estableció límites inferiores exponenciales ajustados 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 un tamaño${\displaystyle \exp(\Omega (n^{\frac {1}{k-1}}))}$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 tamaño${\displaystyle \exp(O(n^{\frac {1}{k-1}})t)}$.

Una función de paridad infinita es una función${\displaystyle f\colon \{0,1\}^{\omega }\to \{0,1\}}$mapear cada cadena binaria infinita a 0 o 1, teniendo la siguiente propiedad: si${\displaystyle w}$y${\displaystyle v}$Si las cadenas binarias infinitas difieren solo en un número finito de coordenadas, entonces${\displaystyle f(w)=f(v)}$si y solo si${\displaystyle w}$y${\displaystyle v}$difieren en un número par de coordenadas.

Suponiendo el axioma de elección se puede demostrar que existen funciones de paridad y que hay${\displaystyle 2^{2^{\aleph _ {0}}}}$muchos de ellos; tantos como el número de todas las funciones de${\displaystyle \{0,1\}^{\omega }}$a${\displaystyle \{0,1\}}$. Basta con tomar un representante por clase de equivalencia de relación${\displaystyle \approx }$definido de la siguiente manera:${\displaystyle w\approx v}$si${\displaystyle w}$y${\displaystyle v}$difieren en un número finito de coordenadas. Teniendo tales representantes, podemos mapearlos todos a${\displaystyle 0}$; el resto de${\displaystyle f}$Los valores se deducen de forma inequívoca.

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

Es necesario asumir al menos cierta cantidad de elección para demostrar que existen funciones de paridad infinitas. Si${\displaystyle f}$es una función de paridad infinita y consideramos la imagen inversa${\displaystyle f^{-1}[0]}$como un subconjunto del espacio de Cantor${\displaystyle \{0,1\}^{\omega }}$, entonces${\displaystyle f^{-1}[0]}$es un conjunto no mensurable 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 medibles 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.

• 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 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