Análisis de una red neuronal para la identificación de funciones booleanas complejas

Abstract

El objetivo de este trabajo es proponer una posible estrategia a largo plazo para abordar el problema P vs. NP, basado en estudiar la clase P/poly y la complejidad de circuitos booleanos. La principal peculiaridad de nuestra estrategia es que tratará de llevarnos al conocimiento teórico a través de una vía empírica. Emplearemos para ello redes neuronales, y analizaremos tanto su estructura como su rendimiento. Con el conocimiento que ganemos podremos confirmar, sustentar o desmentir nuestras hipótesis teóricas, o incluso formular hipótesis nuevas. Por un lado, formalizaremos nociones relacionadas con la repetitividad de funciones booleanas, y definiremos métricas asociadas a ellas bajo la suposición de que las funciones más sencillas son más repetitivas. Por otro, trataremos de encontrar patrones en los pesos de una red neuronal entrenada con las tablas de verdad de algunas funciones booleanas, a las que clasifica según el tamaño del circuito mínimo que las computa. Por último, analizaremos cómo se comportan los patrones identificados y las métricas de repetitividad como clasificadores frente a la tablas de verdad mediante el entrenamiento de más redes neuronales.

The goal of this work is to propose a possible long-term strategy to address the P vs. NP problem, based on studying class P/poly and Boolean circuit complexity. The main peculiarity of our strategy is that it will try to attain theoretical knowledge though empirical means. To do this we will use neural networks, and we will analyze both their structure and their performance. With the knowledge obtained we can either confirm, support or refute our theoretical hypotheses; or even formulate new ones. On the one hand, we will formalize notions related to the repetitiveness of Boolean functions, and we will define metrics associated with them under the assumption that simpler functions are more repetitive. On the other hand, we will try to find patterns in the weights of a neural network trained with the truth tables of some Boolean functions, which classifies them according to the size of the minimum circuit that computes them. Finally, by training more neural networks, we will analyze how the identified patterns and repeatability metrics behave as classifiers when put against truth tables.