Identificación experimental de las funciones booleanas que requieren circuitos extensos y aplicación ́al estudio de P vs NP

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