función de paridad

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 .

Definición

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: ${\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 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]   

Complejidad computacional

Algunos de los primeros trabajos sobre complejidad computacional fueron publicados en 1961 por Bella Subbotovskaya, 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] ${\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 ^[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 . ${\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, 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. ${\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 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. Al tener tales representantes, podemos asignarlos todos a 0; el resto de valores se deducen de forma inequívoca. ${\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 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 . ${\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 multidireccional , una implementación física que se utiliza a menudo para controlar la iluminación.

Temas relacionados:

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

Referencias

1. Ingo Wegener , Randall J. Pruim, Teoría de la complejidad , 2005, ISBN 3-540-21045-8 , p. 260  
2. Jukna, Stasys (6 de enero de 2012). Complejidad de la función booleana: avances y fronteras . Medios de ciencia y negocios de Springer. págs. 167-173. ISBN 978-3642245084.
3. Merrick Furst, James Saxe y Michael Sipser, "Paridad, circuitos y jerarquía de tiempo polinomial", Annu. Internacional Síntoma. Found.Computer Sci., 1981, Teoría de los sistemas informáticos , vol. 17, núm. 1, 1984, págs. 13 a 27, doi :10.1007/BF01744431
4. Miklós Ajtai, " -Fórmulas sobre estructuras finitas", Annals of Pure and Applied Logic , 24 (1983) 1–48. ${\displaystyle \Sigma _{1}^{1}}$

• Håstad, Johan (1987), Limitaciones computacionales de circuitos de pequeña profundidad (PDF) , Ph.D. tesis, Instituto de Tecnología de Massachusetts.