Búsqueda de circuitos mínimos para computar el problema Clique

Abstract

A lo largo de las últimas décadas se ha intentado abordar el problema P vs NP de varias maneras. Una de las más interesantes es a través de funciones y circuitos booleanos. Con el fin de aumentar el conocimiento de este campo, presentamos en este texto un análisis sobre cómo se comportan los circuitos que computan el problema clique. Desarrollamos en detalle uno de los grandes resultados sobre circuitos monótonos: cualquier circuito monótono que compute clique necesita una cantidad superpolinómica de puertas. Después, estudiamos cómo se comportan dos métricas bajo el problema del clique. Analizamos una métrica semántica que se centra en la precisión de los resultados y una métrica sintáctica que se centra en las estructura de las funciones. Por último, realizamos experimentos y simulaciones con ambas métricas en grafos de 8 vértices y cliques de tamaño 4.

Over the last decades, several attemps have been made to address the P vs NP problem. One of the most interesting ways is through boolean functions and circuits. In order to enhance the knowledge in this area, we present in this text an analysis about how the circuits that compute the clique problem behave. We elaborate on one of the great results in monotone circuits: every monotone circuit that computes the clique problem needs a superpolynomial amount of gates. Next, we study hoy two metrics behave under the clique problem. We analyze a semantic metric that focuses on the accuracy of results and a syntactic metric that focuses on the structure of functions. Finally, we perform experiments and simulations with both metrics on 8-vertex graphs and cliques of size 4.