En matemáticas , una función booleana evasiva (de variables) es una función booleana para la cual cada algoritmo de árbol de decisión tiene un tiempo de ejecución de exactamente . En consecuencia, cada algoritmo de árbol de decisión que representa la función tiene, en el peor de los casos, un tiempo de ejecución de .
El tipo de algoritmos considerados en la definición de función booleana evasiva son árboles de decisión en los que cada nodo interno prueba el valor de una de las variables booleanas dadas y se ramifica en consecuencia. Cada nodo hoja del árbol especifica el valor de la función para las entradas que llegan a ese nodo. La complejidad del árbol de decisión en el peor caso de un árbol de decisión dado es el número de variables examinadas en la ruta más larga de raíz a hoja del árbol. Cada función de -variable tiene un algoritmo de árbol de decisión que examina exactamente las variables en todas las entradas, utilizando un árbol de decisión en el que todos los nodos en el nivel prueban la variable th. Una función es evasiva si ningún otro árbol de decisión para la misma función tiene una complejidad menor. Para una función evasiva, cualquier árbol de decisión debe tener al menos una entrada que conduzca a una ruta en el árbol a lo largo de la cual se examinan todas las variables de entrada. [1]
Es trivial construir funciones no evasivas construyendo árboles de decisión en los que cada rama termina antes de probar todas las variables. Por ejemplo, la función siempre verdadera tiene un árbol de decisión sin pruebas. Para un ejemplo menos trivial, en el que se usan todas las variables para determinar el valor de la función, considere la función de tres variables , , y que devuelve o según si es verdadera o falsa respectivamente. Tiene un árbol de decisión que primero prueba , y luego prueba solo uno de o en cada rama.
Si una rama de un árbol de decisión termina antes de probar todas las variables, entonces da el valor de la función para un número par de combinaciones de argumentos: combinaciones, donde es el número de variables y es el número probado a lo largo de esa rama. Por lo tanto, si una función booleana tiene un número impar de combinaciones de argumentos para los cuales es verdadera, entonces debe ser evasiva. [1] Por ejemplo, las funciones lógicas y y o son verdaderas para 1 y combinaciones de argumentos, respectivamente, los cuales son números impares (para ), por lo que son evasivas.
El concepto de función evasiva se introdujo en relación con el estudio de algoritmos de grafos para grafos definidos en un modelo de grafo implícito , donde un algoritmo tiene acceso al grafo solo a través de una subrutina para probar la adyacencia de los vértices. En esta aplicación, una propiedad de grafo puede describirse como una función booleana cuyas variables de entrada son verdaderas si hay una arista entre dos vértices, y una propiedad es evasiva si cada algoritmo debe (en algunas entradas) probar la existencia de cada arista potencial. Los primeros trabajos en esta área demostraron que se debe probar una fracción constante de aristas para cualquier propiedad de grafo monótona no trivial; aquí "no trivial" significa que la función tiene más de un valor, y "monótona" significa que agregar aristas a un grafo no puede cambiar el valor de la función de verdadero a falso. Estos resultados parciales motivaron la formulación de la conjetura de Aanderaa–Karp–Rosenberg , aún no probada, según la cual todas las propiedades de grafo monótonas no triviales son evasivas. [1]
La conjetura de Aanderaa–Karp–Rosenberg se desprendería de una conjetura más general sobre la evasividad de las funciones booleanas: que toda función booleana monótona no trivial que tenga simetrías que lleven cualquier variable a cualquier otra variable es evasiva. Esta conjetura también sigue sin demostrarse, pero se sabe que es cierta para ciertos valores de , incluidas las potencias primos . [1] [2] Se la ha llamado conjetura de la evasividad . [3]
