En matemáticas y ciencias de la computación , una función booleana balanceada es una función booleana cuya salida produce tantos 0 como 1 en su conjunto de entrada . Esto significa que para una cadena de bits de entrada uniformemente aleatoria, la probabilidad de obtener un 1 es 1/2. [1]
Ejemplos de funciones booleanas balanceadas son la función mayoritaria , [1] la "función dictadura" que copia el primer bit de su entrada a la salida, [1] y la función de verificación de paridad que produce la o exclusiva de los bits de entrada. [2]
Si es una función doblada sobre bits, y es cualquier vector de bits distinto de cero, entonces la función que se asigna a está balanceada. Las funciones dobladas son exactamente las funciones para las que esto es cierto, para todas las opciones distintas de cero de . [3]
La función de dictadura se puede evaluar después de examinar un solo bit de la entrada, pero ese bit siempre debe examinarse. Benjamini, Schramm y Wilson describen un ejemplo más complejo basado en la teoría de la percolación con la propiedad de que un algoritmo aleatorio de Las Vegas puede calcular la función con exactitud mientras garantiza que la probabilidad de leer cualquier bit de entrada en particular sea pequeña, aproximadamente inversamente proporcional a la raíz cuadrada del número de bits. [1]
Las funciones booleanas balanceadas se utilizan en criptografía , donde estar balanceado es uno de "los criterios más importantes para funciones booleanas criptográficamente fuertes". [3] Si una función no está balanceada, tendrá un sesgo estadístico , lo que la hace sujeta a criptoanálisis como el ataque de correlación .
