Publication: Identificación experimental de las funciones booleanas que requieren circuitos extensos y aplicación ́al estudio de P vs NP
Loading...
Official URL
Full text at PDC
Publication Date
2021-06
Authors
Advisors (or tutors)
Rodr ́ıguez Laguna, Ismael
Editors
Journal Title
Journal ISSN
Volume Title
Publisher
Citations
Exportar
Abstract
En este trabajo se han tratado de explorar, mediante la vía empírica, aspectos relacionados con la complejidad computacional de circuitos booleanos que podrían resultar fundamentales en una hipotética resolución del problema P vs NP. M ́as concretamente, el trabajo se ha enfocado en determinar qué factores influyen para que una determinada función booleana pueda ser computada mediante un circuito “peque ̃no” (es decir, con pocas puertas lógicas) o que, por contra, requiera de un circuito “grande”. Si un problema está en P, entonces existen circuitos booleanos, uno por cada tamaño n de entrada, que resuelven el problema con un tamaño polinómico respecto a n. Por contrapositivo, si dichos circuitos no existen, el problema no está en la clase P. Por eso, averiguar qué funciones booleanas requieren circuitos “grandes” podría ser clave para demostrar la no pertenencia de ciertos problemas a la clase P (y por tanto, para tratar de demostrar que NP no está contenido en P). Este trabajo comenzó con el desarrollo de un generador sistemático de circuitos que permitió obtener una tabla de funciones booleanas junto al tamaño de un circuito mínimo que las computaba. Dicha tabla sirvió como dataset para los experimentos posteriores, enfocados ya en determinar los factores que buscábamos. Para ello, fue fundamental una generación de circuitos suficientemente astuta, como para que la cantidad y calidad de los datos permitiera después obtener buenos resultados. Posteriormente, se lanzaron diversas conjeturas fundamentadas tanto en una primera inspección visual de los datos, como en diversos aspectos intuitivos, cotejando todas nuestras hipótesis después sobre el dataset. Para valorar dichas conjeturas sobre los datos, se diseñaron varias métricas que permitieron cuantificar numéricamente cómo de ciertas eran nuestras hipótesis. De esta forma, se pudo decidir con cuáles de ellas era conveniente quedarse, debido a su buen comportamiento sobre los datos, y cuáles debían ser rechazadas. Para el estudio de los datos resultó fundamental el hecho de que, por construcción del dataset, las funciones de nuestra tabla fueran exactamente las que podían computarse con los circuitos más pequeños. Esto supone que la tabla no solo contiene información sobre las funciones que aparecen anotadas en ella, sino también, en cierto modo, sobre todas las demás funciones, que al menos necesitarán el tamaño máximo que se ha llegado a anotar en la tabla para computarse. Debido a ello, se pudo suponer que las funciones de nuestra tabla eran las computables con circuitos “pequeños” y las funciones del complementario eran las que necesitaban circuitos “grandes”. Como teníamos
que establecer cierta frontera entre “grande” y “pequeño” y, por construcción, las funciones complementarias a nuestro dataset requerían al menos tanto tamaño como el máximo del dataset, nos pareció razonable fijar esta frontera exactamente en el l ́ımite alcanzado por el experimento. No solo se pudo comprobar el buen funcionamiento de nuestras métricas sobre los datos, sino también corroborar un comportamiento opuesto sobre ejemplos aleatorios del complementario. Además, dicha suposición fue claramente refrendada por varios de nuestros experimentos, lo cual sustenta que es adecuado hacerla. Seguidamente, ya con unas buenas métricas que aportaban cierto conocimiento sobre los datos, y que constituían algunos de los tan ansiados factores que buscábamos, se pasó a utilizar diversas técnicas de Aprendizaje Automático en busca de m ́as factores. Los resultados fueron muy esperanzadores e interesantes en el sentido de que reforzaron enormemente el buen quehacer de nuestras métricas y dejaron entrever fuertes patrones de diferenciación entre nuestra tabla y el complementario. Pero, sin embargo, tuvieron la desventaja de no ser fácilmente comprensibles. Se utilizaron redes neuronales que, aunque obtuvieron unos resultados excelentes, presentaban como handicap la imposibilidad de entender lo aprendido m ́as allá de un producto de matrices aplicado a las entradas. Nuestro propósito era descubrir propiedades generales con una explicación lógica detrás y desde el principio temíamos que la vía del Aprendizaje Automático diese problemas en ese sentido. Por eso sólo se exploró esta opción una vez obtenidas métricas que nos aseguraban haber cumplido ciertos objetivos. Aunque sin mucho ́exito, se trataron de analizar los pesos de las redes para descifrar los patrones que podían haber aprendido. Se consiguieron extraer ciertas conclusiones en base a los resultados para distintas topologías de red que, en cierto modo, reflejaban la naturaleza de lo aprendido sin terminar de concretarlo pero, simplemente observando los pesos, no se encontró un patrón concreto suficientemente claro. Un estudio mucho m ́as profundo y exhaustivo de los pesos requería una inversión de tiempo que, a esas alturas del trabajo, podía resultar excesiva poniendo en riesgo otros experimentos. Además, era una tarea que podía resultar poco fructífera al no haber ninguna garantía de que aquello que la red hubiese aprendido siguiera un patrón claro, sencillo y entendible para un ser humano. Por todo ello, se decidió pasar a otros asuntos dejando un hilo suelto del que seguir tirando en el futuro. El broche final lo pusimos tratando de comprobar que, en efecto, las métricas y modelos obtenidos permitían, en cierto modo, diferenciar entre problemas de la clase P y problemas NP-completos. Esto es algo muy osado, pues constituiría un especie de test empírico de que P 6= NP, lo cual parecía difícil desde experimentos tan humildes como los nuestros. Por ello, no esperábamos grandes resultados, como mucho algún indicio o curiosidad. Este experimento final presentaba varias dificultades. Para empezar, no era automatizable para una gran cantidad de problemas, pues la manera de resolver cada uno de ellos era particular. Se resolvió el problema
NP-completo Cliqué (para grafos de 7 vértices) y el problema Paridad de la clase P. La elección de este problema NP-completo fue debida a la facilidad para codificar instancias medianamente interesantes con un número de bits no demasiado grande, de forma que el cálculo de la tabla de verdad resultase computable. El otro gran conflicto tenía que ver con la dificultad computacional de aplicar los modelos y métricas obtenidos
sobre una tabla de verdad formada por millones de bits. Para solventar esto, se decidió hacer un muestreo de la tabla, aun a riesgo de que los resultados pudieran distorsionarse. Para que el muestreo fuese interesante y permitiese cotejar si los modelos encerraban algo interesante, se sesgó dicho muestreo hacia las partes más complicadas de los problemas NP-completos. Las dificultades de los problemas NP-completos se concentran, en su tabla de verdad, dentro de una especie de frontera que separa instancias complicadas de otras que son bastante triviales. Por ello, la idea fue comparar los resultados de nuestros modelos para la parte complicada de estas tablas, frente al resultado de instancias de problemas de la clase P que, a priori, podrían ser igual de difíciles. De esta forma, pudimos comprobar que algunos de nuestros modelos efectivamente habían conseguido captar las dificultades especiales que presentan los problemas NP-completos. Aunque los resultados no fueron todo lo claros que nos habría gustado, hay que tener en cuenta que están muy condicionados por el tamaño de las secuencias de bits analizadas, que eran muy pequeñas en relación a los millones de bits que formaban la secuencia total. Pero, teniendo en cuenta que el reto era muy grande y que no había muchas m ́as opciones, podemos darnos por satisfechos con lo obtenido.
In this work, we empirically explore different properties of Boolean circuits related to their computational complexity, which can be of great interest when approaching the P vs NP problem. In particular, we focus on determining the factors influencing the size or depth of the Boolean circuits that compute a certain Boolean function (i. e., we study what makes the function computable via a small circuit, with few logic gates, or a big circuit). It is important to notice that, for P problems, there exist Boolean circuits (one for each input size n) of polynomial size with respect to the input that can solve the problem. Conversely, the contrapositive states that whenever these circuits do not exist, then the problem is not in P. For this reason, studying what Boolean functions require big circuits to compute them could be a key to proving that there are certains problems in NP that do not belong to P (and therefore showing that P 6= NP). Firstly, we developed a systematic circuit generator which allowed us to obtain the truth tables for different Boolean functions along with the size of the smallest circuits that compute it. The tables obtained were also used as datasets for later experimentation, which was focused on uncovering the determining factors we were looking for. With the intention of accomplishing this, we had to cunningly generate circuits to ensure that enough data was available, while we assured the quality of it. Afterwards, we came up with several conjectures based on a first visual inspection of the data, as well as on different intuitive features detected. All of the assumptions were tested against the datasets. To assess all of the hypotheses, we designed several metrics to quantify the number of elements behaving as assumed. Thus, we could decide which ones were great fits for the data, and which ones should be discarded. When studying the data it was essential to have the functions that could be computing using the smallest circuits. Hence, the truth tables do not only contain the information regarding the related functions, but they also shed light on the rest of the functions since, at least, they would require a circuit of size greater than or equal to the one depicted in the table. In consideration of the foregoing, we could assume that the functions related to the tables were the ones computable via the smallest circuits, and the complementary ones were linked to big circuits. On the other hand, since we needed to establish a barrier between what we meant as small or big circuit sizes, we thought it was quite reasonable to set this limit as the one reached by the experiment itself (note that the complementary functions required a size no less than the one of the original datasets). Fortunately, we found out that not only the metrics reported great results on our dataset, but they also behaved appropriately for random complementary examples. Moreover, this behaviour was endorsed by several of our experiments on the data, supporting the methodology. Subsequently, once we had great metrics to enlighten us with regard to the data, and which were themselves the factors we longed for, we started to apply different Machine Learning techniques. The results were really encouraging since they greatly supported the performance of our metrics, while they revealed contrastive patterns to differentiate between the tables generated and their complementary. However, the lack of interpretability in these techniques prevent us from gaining more insight about this. We implemented neural network models that reported excellent results, but inner workings were not easy to grasp. Because our main goal was to figure out properties along with logical explanations on why they emerged, we were already concerned from the very first moment with the explainability and interpretability issue of Machine Learning approaches. Indeed, that is why we only applied these techniques after exploring the metrics which already met our initial objectives. We studied the weights of the neural networks to try to unravel the implicit patterns learned, with modest success. We extracted several conclusions regarding the results obtained using different topologies, which in some sense reflect the nature of what was learned. Unfortunately, just by simple inspection on the weights it was not possible to conclude any key factor. Besides, since a deeper and comprehensive review of the model requires a great investment of time, we could not venture more into this. Further research in this matter is required, and it could potentially clear up the patterns learned by the models. We put the finishing touches on this work by trying to verify that the metrics and models obtained allowed us, to some extent, to differentiate clearly between P and NP-Complete problems. This daring task could be conceived also as an empirical test to show that P 6= NP, a problem which at the beginning of this work looked unaddressable. This final experiment presented some challenges. Firstly, it was not allowing automation in a wide range of problems, since the way every problem was solved was different. We solved the NP-complete Clique problem (for 7-vertices graphs), and the Parity problem of the P class. The choice of this NP-complete problem was based on the ease of coding quite interesting instances with a not too large number of bits, so that the computation of the truth table was feasible. The other vast challenge was related to the computational complexity of applying the models and metrics retrieved to a truth table composed of millions of bits. To solve this, we decided to sample the table, assuming that the results could be distorsioned as a risk. For making the sampling more interesting, and for allowing us to check whether the models were hiding something crucial, we skewed it to take the hardest parts of the NP-complete problems. The difficulties of these problems are located, in their truth table, inside a frontier that separates the complex instances from the trivial ones. Therefore, we had the idea of comparing the results of our models for those complex locations, with the results of the instances of problems of P class that, a priori, seemed to have the same difficulty. In this way, we were able to check that some of our models, indeed, had managed to capture the special difficulties that NP-complete problems present. Although the results were not as clear as we would have desired, we should take into consideration that they are very conditioned by the length of the analyzed bits sequences, which were really small in comparison to the millions of bits that are part of the complete sequence. However, considering the hallenge was great and ambitious, and that there were no further options, we could be satisfied with the results obtained.
In this work, we empirically explore different properties of Boolean circuits related to their computational complexity, which can be of great interest when approaching the P vs NP problem. In particular, we focus on determining the factors influencing the size or depth of the Boolean circuits that compute a certain Boolean function (i. e., we study what makes the function computable via a small circuit, with few logic gates, or a big circuit). It is important to notice that, for P problems, there exist Boolean circuits (one for each input size n) of polynomial size with respect to the input that can solve the problem. Conversely, the contrapositive states that whenever these circuits do not exist, then the problem is not in P. For this reason, studying what Boolean functions require big circuits to compute them could be a key to proving that there are certains problems in NP that do not belong to P (and therefore showing that P 6= NP). Firstly, we developed a systematic circuit generator which allowed us to obtain the truth tables for different Boolean functions along with the size of the smallest circuits that compute it. The tables obtained were also used as datasets for later experimentation, which was focused on uncovering the determining factors we were looking for. With the intention of accomplishing this, we had to cunningly generate circuits to ensure that enough data was available, while we assured the quality of it. Afterwards, we came up with several conjectures based on a first visual inspection of the data, as well as on different intuitive features detected. All of the assumptions were tested against the datasets. To assess all of the hypotheses, we designed several metrics to quantify the number of elements behaving as assumed. Thus, we could decide which ones were great fits for the data, and which ones should be discarded. When studying the data it was essential to have the functions that could be computing using the smallest circuits. Hence, the truth tables do not only contain the information regarding the related functions, but they also shed light on the rest of the functions since, at least, they would require a circuit of size greater than or equal to the one depicted in the table. In consideration of the foregoing, we could assume that the functions related to the tables were the ones computable via the smallest circuits, and the complementary ones were linked to big circuits. On the other hand, since we needed to establish a barrier between what we meant as small or big circuit sizes, we thought it was quite reasonable to set this limit as the one reached by the experiment itself (note that the complementary functions required a size no less than the one of the original datasets). Fortunately, we found out that not only the metrics reported great results on our dataset, but they also behaved appropriately for random complementary examples. Moreover, this behaviour was endorsed by several of our experiments on the data, supporting the methodology. Subsequently, once we had great metrics to enlighten us with regard to the data, and which were themselves the factors we longed for, we started to apply different Machine Learning techniques. The results were really encouraging since they greatly supported the performance of our metrics, while they revealed contrastive patterns to differentiate between the tables generated and their complementary. However, the lack of interpretability in these techniques prevent us from gaining more insight about this. We implemented neural network models that reported excellent results, but inner workings were not easy to grasp. Because our main goal was to figure out properties along with logical explanations on why they emerged, we were already concerned from the very first moment with the explainability and interpretability issue of Machine Learning approaches. Indeed, that is why we only applied these techniques after exploring the metrics which already met our initial objectives. We studied the weights of the neural networks to try to unravel the implicit patterns learned, with modest success. We extracted several conclusions regarding the results obtained using different topologies, which in some sense reflect the nature of what was learned. Unfortunately, just by simple inspection on the weights it was not possible to conclude any key factor. Besides, since a deeper and comprehensive review of the model requires a great investment of time, we could not venture more into this. Further research in this matter is required, and it could potentially clear up the patterns learned by the models. We put the finishing touches on this work by trying to verify that the metrics and models obtained allowed us, to some extent, to differentiate clearly between P and NP-Complete problems. This daring task could be conceived also as an empirical test to show that P 6= NP, a problem which at the beginning of this work looked unaddressable. This final experiment presented some challenges. Firstly, it was not allowing automation in a wide range of problems, since the way every problem was solved was different. We solved the NP-complete Clique problem (for 7-vertices graphs), and the Parity problem of the P class. The choice of this NP-complete problem was based on the ease of coding quite interesting instances with a not too large number of bits, so that the computation of the truth table was feasible. The other vast challenge was related to the computational complexity of applying the models and metrics retrieved to a truth table composed of millions of bits. To solve this, we decided to sample the table, assuming that the results could be distorsioned as a risk. For making the sampling more interesting, and for allowing us to check whether the models were hiding something crucial, we skewed it to take the hardest parts of the NP-complete problems. The difficulties of these problems are located, in their truth table, inside a frontier that separates the complex instances from the trivial ones. Therefore, we had the idea of comparing the results of our models for those complex locations, with the results of the instances of problems of P class that, a priori, seemed to have the same difficulty. In this way, we were able to check that some of our models, indeed, had managed to capture the special difficulties that NP-complete problems present. Although the results were not as clear as we would have desired, we should take into consideration that they are very conditioned by the length of the analyzed bits sequences, which were really small in comparison to the millions of bits that are part of the complete sequence. However, considering the hallenge was great and ambitious, and that there were no further options, we could be satisfied with the results obtained.
Description
Trabajo de Fin de Grado en Ingeniería Informática, Facultad de Informática UCM, Departamento de Sistemas Informáticos y Computación, Curso 2020-2021.