Publication: Analysis of Boolean functions using equanimity and entanglement
Loading...
Official URL
Full text at PDC
Publication Date
2023
Advisors (or tutors)
Editors
Journal Title
Journal ISSN
Volume Title
Publisher
Citations
Exportar
Abstract
The study of Boolean functions has made limited progress in recent years. Despite significant efforts, fundamental questions regarding the complexity and behavior of Boolean functions remain unresolved. The lack of comprehensive mathematical models and techniques hinders advancements in this field, leaving many open questions and avenues for future research. In this work, we aim to expand our limited knowledge in this field by proposing and studying two notions that could help unravel when a Boolean function is computed by super-polynomial circuits. The first notion is equanimity, which captures the condition where the output of a Boolean function is equally influenced by all input variables and/or subsets of the input. We will observe that this definition is not capable of classifying when a function cannot be computed by a polynomial circuit, although it remains a good indicator. Therefore, we need to introduce another concept, namely entanglement. This concept measures the amount of information needed from each subset of the input variables in order to obtain the output of the function. Finally, we will provide empirical evidence that a highly entangled and highly equanimous function must necessarily be computed by large circuits, ideally super-polynomial ones. This could lead to a potential new approach to demonstrate that P ̸= NP.
El estudio de las funciones booleanas ha tenido un progreso limitado en los últimos años. A pesar de algunos resultados significativos, quedan todavía muchas preguntas fundamentales sobre la complejidad y el comportamiento de las funciones booleanas. La falta de modelos matemáticos completos y técnicas exhaustivas obstaculiza los avances en este campo, dejando muchas preguntas abiertas y vías para futuras investigaciones. En este trabajo, tenemos como objetivo ampliar nuestro conocimiento limitado en este campo al proponer y estudiar dos conceptos que podrían ayudar a desentrañar cuándo una función booleana es calculada por circuitos superpolinómicoss. El primer concepto es el de ecuanimidad, que pretende capturar cuándo una función booleana es igualmente influenciada por todas las variables de entrada o subconjuntos de la entrada. Observaremos que esta definición no es capaz de clasificar cuándo una función no puede ser calculada por un circuito polinómico, aunque sigue siendo un buen indicador. Por lo tanto, necesitamos introducir el otro concepto, el de enredo. Este concepto mide la cantidad de información necesaria de cada subconjunto de las variables de entrada para obtener la salida de la función. Finalmente, proporcionaremos evidencia empírica de que una función altamente enredada y ecuánime debe ser necesariamente computada por circuitos grandes, idealmente superpolinómicos. Esto podría conducir a un nuevo enfoque prometedor para demostrar que P ̸= NP.
El estudio de las funciones booleanas ha tenido un progreso limitado en los últimos años. A pesar de algunos resultados significativos, quedan todavía muchas preguntas fundamentales sobre la complejidad y el comportamiento de las funciones booleanas. La falta de modelos matemáticos completos y técnicas exhaustivas obstaculiza los avances en este campo, dejando muchas preguntas abiertas y vías para futuras investigaciones. En este trabajo, tenemos como objetivo ampliar nuestro conocimiento limitado en este campo al proponer y estudiar dos conceptos que podrían ayudar a desentrañar cuándo una función booleana es calculada por circuitos superpolinómicoss. El primer concepto es el de ecuanimidad, que pretende capturar cuándo una función booleana es igualmente influenciada por todas las variables de entrada o subconjuntos de la entrada. Observaremos que esta definición no es capaz de clasificar cuándo una función no puede ser calculada por un circuito polinómico, aunque sigue siendo un buen indicador. Por lo tanto, necesitamos introducir el otro concepto, el de enredo. Este concepto mide la cantidad de información necesaria de cada subconjunto de las variables de entrada para obtener la salida de la función. Finalmente, proporcionaremos evidencia empírica de que una función altamente enredada y ecuánime debe ser necesariamente computada por circuitos grandes, idealmente superpolinómicos. Esto podría conducir a un nuevo enfoque prometedor para demostrar que P ̸= NP.
Description
Trabajo de Fin de Doble Grado en Ingeniería Informática y Matemáticas, Facultad de Informática UCM, Departamento de Sistemas Informáticos y Computación, Curso 2022/2023.
Repositorio del presente trabajo en https://github.com/encarro12/TFG-Circuit-Complexity.git