Learning Circuit Complexity of Boolean Functions

Computational Complexity has grappled for decades with understanding which Boolean functions can be computed with small circuits. This knowledge would unlock new ways to approach paramount open problems in Computer Science, such as P vs NP. We present an empirical approach to the problem in which we classify 5-to-l-bit Boolean functions. We built a dataset of functions with small encoding circuits and tested different classifiers to isolate them from the vast complementary set of functions with big circuits. Simple multilayer perceptrons achieved 97% and higher accuracies. We introduce r-weights, a heuristic on neuron weights, to explain how and why this approach was so successful, and we present the theoretical conclusions we extracted from them to face the circuit complexity problem.