Analysis of Minimal Boolean Circuits

Abstract

Circuit complexity, a branch of computational complexity theory, has seen limited progress in establishing lower bounds for the minimum size of circuits that solve NP-complete problems. Existing bounds primarily apply to restricted families of circuits, such as constant-depth or monotone circuits. Identifying an NP problem that requires superpolynomial-size circuits would imply that P ̸= NP, highlighting the difficulty of this challenge. In this work, we propose metrics for analyzing Boolean functions and the circuits that implement them. We apply these metrics to complete sets of minimum-size circuits, with the aim of studying their structure and understanding what makes a function require large circuits.

La complejidad de circuitos, una rama de la teoría de la complejidad computacional, ha mostrado avances limitados en la obtención de cotas inferiores para el tamaño mínimo de circuitos que resuelven problemas NP-completos. Las cotas existentes se aplican principalmente a familias restringidas de circuitos, como los circuitos de profundidad constante o monótonos. Identificar un problema NP que requiera circuitos de tamaño superpolinómico implicaría que P ̸= NP, subrayando la dificultad de este desafío. En este trabajo proponemos métricas para el análisis de funciones booleanas y los circuitos que las implementan. Aplicamos estas métricas a conjuntos completos de circuitos de tamaño mínimo, con el objetivo de analizar su estructura.