Estudio de complejidad de circuitos para el problema CLIQUE

Abstract

En lo referente al problema P vs N P, uno de los campos de estudio que más útil ha demostrado ser en las últimas décadas es el de los circuitos booleanos. En este texto buscamos adentrarnos en esta vía de estudio, concretamente abordando el problema de Clique (n,k). Estudiamos detalladamente uno de los resultados más importantes que se han desarrollado en este campo, que enuncia que cualquier sucesión de circuitos de profundidad constante que compute Clique (n,k) debe tener tamaño superpolinómico. Después de esto, estudiamos este problema de forma experimental, continuando con la vía de estudio propuesta en un trabajo anterior, cuyo objeto de estudio principal es la métrica sintáctica. Contrastamos ciertas hipótesis acerca del posible crecimiento de la puntuación y proponemos de forma teórica varias medidas que describen comportamientos que pueden diferenciar las funciones más productivas de las funciones fácilmente computables. Finalmente, ponemos a prueba estas medidas para el caso de n = 8 y k = 4, exponiendo las diferencias que presentan los distintos tipos de funciones, así como desarrollando un modelo de aprendizaje supervisado que, con base en los valores de las distintas medidas, sea capaz de predecir el tipo de función del que provienen

With regard to the problem P vs N P, one of the fields of study that has proven most useful in recent decades is that of boolean circuits. In this text, we seek to delve deeper into this line of study, specifically addressing the problem of Cliquev(n,k). We study in detail one of the most important results that has been developed in this field, which states that any sequence of constant depth circuits that computes Clique (n,k) must be superpolynomial in size. After this, we study this problem experimentally, continuing with the line of study proposed in a previous work, whose main object of study is the syntactic metric. We contrast certain hypotheses about the possible growth of the score, and we propose several theoretical measures which describe behaviors that can differentiate the most productive functions from easily computable functions. Finally, we test these measures for the case of n = 8 and k = 4, exposing the differences between the different types of functions, as well as developing a supervised learning model that, based on the values of the different measures, is capable of predicting the type of function from which they originate.