Universidad Complutense de Madrid Facultad de Informática Bachelor’s Thesis in Computer Science Double Degree in Mathematics and Computer Science Analysis of Boolean functions using equanimity and entanglement Análisis de funciones booleanas utilizando ecuanimidad y enredo Authors: Enrique Carro Garrido José Ramón Cobián Fernández Directors: Ismael Rodríguez Laguna Narciso Martí Oliet Madrid, 29th May 2023 Abstract The study of Boolean functions has made limited progress in recent years. Despite sig- nificant efforts, fundamental questions regarding the complexity and behavior of Boolean functions remain unresolved. The lack of comprehensive mathematical models and tech- niques hinders advancements in this field, leaving many open questions and avenues for future research. In this work, we aim to expand our limited knowledge in this field by proposing and studying two notions that could help unravel when a Boolean function is computed by super-polynomial circuits. The first notion is equanimity, which captures the condition where the output of a Boolean function is equally influenced by all input variables and/or subsets of the input. We will observe that this definition is not capable of classifying when a function cannot be computed by a polynomial circuit, although it remains a good indicator. Therefore, we need to introduce another concept, namely entanglement. This concept measures the amount of information needed from each subset of the input variables in order to obtain the output of the function. Finally, we will provide empirical evidence that a highly entangled and highly equanimous function must necessarily be computed by large circuits, ideally super-polynomial ones. This could lead to a potential new approach to demonstrate that P ̸= NP. Keywords Boolean functions, circuit complexity, P vs. NP, P/poly class, lower bounds of circuits, equanimity, entanglement. ii Resumen El estudio de las funciones booleanas ha tenido un progreso limitado en los últimos años. A pesar de algunos resultados significativos, quedan todavía muchas preguntas funda- mentales sobre la complejidad y el comportamiento de las funciones booleanas. La falta de modelos matemáticos completos y técnicas exhaustivas obstaculiza los avances en este campo, dejando muchas preguntas abiertas y vías para futuras investigaciones. En este trabajo, tenemos como objetivo ampliar nuestro conocimiento limitado en este campo al proponer y estudiar dos conceptos que podrían ayudar a desentrañar cuándo una función booleana es calculada por circuitos superpolinómicoss. El primer concepto es el de ecuanimidad, que pretende capturar cuándo una función booleana es igualmente influenciada por todas las variables de entrada o subconjuntos de la entrada. Observaremos que esta definición no es capaz de clasificar cuándo una función no puede ser calculada por un circuito polinómico, aunque sigue siendo un buen indicador. Por lo tanto, necesitamos introducir el otro concepto, el de enredo. Este concepto mide la cantidad de información necesaria de cada subconjunto de las variables de entrada para obtener la salida de la función. Finalmente, proporcionaremos evidencia empírica de que una función altamente enredada y ecuánime debe ser necesariamente computada por circuitos grandes, idealmente super- polinómicos. Esto podría conducir a un nuevo enfoque prometedor para demostrar que P ̸= NP . Palabras clave Funciones booleanas, complejidad de circuitos, P vs NP, clase P/poly, cotas inferiores de circuitos, ecuanimidad, enredo. iii Contents Abstract ii 1. Introduction 1 2. State of the art 4 2.1. P vs NP Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2. Techniques to solve P vs NP . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3. Circuit complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3. Presentation of the new approach 10 3.1. Equanimity and entanglement . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.2. Decision problems of interest . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.2.1. Problems known to be in P/poly . . . . . . . . . . . . . . . . . . . . 12 3.2.2. CLIQUE Decision Problems . . . . . . . . . . . . . . . . . . . . . . 14 3.3. Experiments to support the conjecture . . . . . . . . . . . . . . . . . . . . 17 4. Equanimity 19 4.1. Introduction to the concept of equanimity . . . . . . . . . . . . . . . . . . 19 4.2. Equanimity based on the importance of each variable . . . . . . . . . . . . 21 4.2.1. Implementation for QI . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.3. Equanimity based on the survival of subsets . . . . . . . . . . . . . . . . . 23 4.3.1. Alternative to the definition . . . . . . . . . . . . . . . . . . . . . . 25 4.3.2. Implementation for QS . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.4. Limits of equanimity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5. Entanglement 30 5.1. Introduction to the concept of entanglement . . . . . . . . . . . . . . . . . 30 5.2. Entanglement formal definition . . . . . . . . . . . . . . . . . . . . . . . . 34 5.3. Properties of entanglement metric . . . . . . . . . . . . . . . . . . . . . . . 36 5.4. Implementation for T . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 iv Contents v 5.5. Do we still need equanimity? . . . . . . . . . . . . . . . . . . . . . . . . . . 41 6. Experimental results 43 6.1. Performance of metrics in the dataset . . . . . . . . . . . . . . . . . . . . . 43 6.1.1. Testing the metrics individually . . . . . . . . . . . . . . . . . . . . 43 6.1.2. Testing metrics combined . . . . . . . . . . . . . . . . . . . . . . . 48 6.2. Scalability of metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 6.3. Mitigating bias in Boolean circuits . . . . . . . . . . . . . . . . . . . . . . 59 6.3.1. Keeping x1 AND x2 in a branch . . . . . . . . . . . . . . . . . . . . 61 6.3.2. Poisoning the first level with x1 AND x2 . . . . . . . . . . . . . . . 62 6.3.3. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 7. Conclusions and future work 65 Personal contributions 67 Bibliography 72 Chapter 1 Introduction Boolean functions play a crucial role in the study of the P vs NP problem. However, in recent years, there has been a lack of significant advancements in the field of Boolean function research. Therefore, any contribution, no matter how small, would be valuable in our collective journey towards finding a solution to the millennium problem. Some interesting progress was made by our former colleagues Jorge Villarrubia [VE21] and Celia Rubio [RM22] in their respective Bachelor’s theses. The objective of our project is to continue expanding our knowledge on the topic via the study of two concepts that, to the best of our knowledge, are novel: equanimity and entanglement1. These properties will help us understand the inner working of functions and the circuits that compute them. In particular, we theorize that if a Boolean function is both equanimous and entangled, then it will inevitably be computed by a big (ideally superpolynomial-sized) circuit. First of all, it is necessary to provide a formal definition of these abstract concepts to be able to operate with them. This process will involve brainstorming and identifying the key aspects of each concept, as well as evaluating their behavior within specific decision problems. This way, we will be able to adjust and perfect these definitions. Then, we will test how they work by conducting tests on a set of functions computed by small circuits and another set of functions computed by larger circuits. This is motivated by our expectation that the metrics will yield distinct values depending on the circuit’s size. In consequence, they will be useful to determine particular behaviors that prevent the circuits that compute a function from having polynomial size. Following that, we will analyze the results in order to determine if the metrics are indeed a good indicator. Moreover, additional experiments will be carried out to gather further information and insights. Finally, the collection of all the results will help us determine the viability of our con- 1Our notion of entanglement will be somehow inspired by quantum entanglement from physics, al- though we are not aware of any applications of related ideas to the classification of Boolean functions. 1 2 Chapter 1. Introduction jecture. Based on these findings, we will explain how this approach can be pursued in future works, ultimately bringing us closer to advancing our understanding of the P vs NP problem. In the subsequent paragraphs, we will outline the structure of the report and provide an overview of the content covered in each chapter. In Chapter 2, we provide a detailed overview of the background of this work. It formally describes the P vs NP problem and then outlines the main proof techniques that have been utilized since its conception in 1970. Finally, we focus on the technique that we consider the most promising but with very few advancements: Circuit complexity. In Chapter 3, we present a developed framework of the methodology we propose and the specific objectives of this work, stating our conjecture regarding the relationship between circuit size and high values of equanimity and entanglement. We provide an “a priori” description of these abstract concepts. Then, we outline the decision problems of interest that we use as benchmarks for our metrics, and finally we list the various experiments we conducted to provide empirical support for the conjecture. In the following chapters, we focus on systematically developing this methodology step by step. In Chapter 4, we study the concept of equanimity. The chapter is structured in such a way that we begin with an introduction to this abstract concept, followed by a formal definition of it. Within the same formalization, we explore two distinct approaches to the concept: one based on variable importance and another based on the survival of subsets of the input. Once the formal definition is provided, we proceed to discuss and analyze the cost of its different implementations. Finally, we present the limits of equanimity, setting the stage for the next chapter, which explains the concept of entanglement. In Chapter 5, we follow the same structure as the previous chapter to present the concept of entanglement. We begin with an introduction to the concept, followed by its formaliza- tion. We then proceed to demonstrate certain properties that hold for this metric. Similar to equanimity, we provide the implementation of the metric and analyze its computational cost. The last section of this chapter is dedicated to arguing that entanglement alone may not function properly, thereby emphasizing the continued need for equanimity. Chapter 6 presents the results of three experiments conducted to provide empirical support for our initial hypothesis. The first experiment involves testing the metric using the dataset provided by José Ramón Cobián [CF23]. In the second experiment, we explore the scalability of the metrics by examining how the metric values behave for the given benchmark problems as the input size increases. The final experiment focuses on testing the metrics using a specific type of circuits known as alternating circuits. In Chapter 7, we will present our deductions and the results obtained from our studies. 3 We will be able to ultimately conclude whether the method we propose is suitable for our purpose in identifying complex Boolean functions. Finally, we will describe some future directions for our work with the ideal goal of providing useful insights for anyone attempting to ultimately solve the P vs NP problem. Chapter 2 State of the art The P vs NP question is central in theoretical computer science [Wig06]. The challenge of solving this problem, together with the need to understand the power and limits of computation, has led to the development of computational complexity theory. The dis- cussion of progress includes diagonalization, algebrization, natural proofs barriers and other techniques [AS16]. This problem is considered one of the great problems of science. Another interesting approach to face the P vs NP problem is obtaining circuit lower bounds, which has led to circuit complexity theory. It seems more than reasonable that problems should be analyzed by visualizing what is happening locally, which is the aim of circuit complexity theory. However, this area is usually overlooked and not given proper attention. 2.1. P vs NP Problem With the aim of understanding this problem, we have to determine what P and NP classes are. First, we have to define the type problems that will be considered and what being efficiently computable means in this context. Definition 2.1.1 (Decision problem). A decision problem is a problem that can be ex- pressed as a yes-or-no answer of the input. A problem can be computed if there exists a set of rules that, followed in a particular way, may solve it. This fixed set of rules is called algorithm. In order to compute a problem, these rules could be applied multiple times, making the algorithm take more time. This is why we will measure computational efficiency as the number of basic operations an algorithm performs, which has to be a function of its input length. In order to formalize this concept, not depending on the formalism chosen, Turing intro- duced Turing machines. 4 2.1. P vs NP Problem 5 We’re not going to go into detail about Turing machines, so we will introduce an informal definition to give an idea of what they are. Definition 2.1.2 (Turing machines). [Tur36] A Turing machine is an abstract machine consisting of a one-dimensional infinite tape divided into cells, each capable of containing one symbol. It has a finite set of rules that determine how the machine should behave based on the current symbol being read and the machine’s internal state. If there is only one pos- sible transition from one state to another, we say the Turing machine is deterministic. Otherwise, we say it is non-deterministic. In order to group certain problems based on similarities on the way they are computed, complexity classes were created. There exists a lot of them, with a broad range of speci- ficity, so we will introduce the most remarkable ones. Definition 2.1.3 (The class P). The class P contains all the decision problems that can be computed in polynomial time by a deterministic Turing machine. Most known algorithms that solve problems in P run in O(nk) for a low value of k, so these problems are also called tractable. Definition 2.1.4 (The class NP). The class NP contains all the decision problems that can be computed in polynomial time by a non-deterministic Turing machine. Alternatively, the class NP can be defined as the set of all the decision problems such that, if a certificate (a potential proof indicating a "yes" answer) of polynomial size is provided, then a deterministic Turing machine can verify in polynomial time whether the guess is correct or not. For example, a certificate of the Hamiltonian path problem (find a path in a graph that visits each vertex exactly once) would be a sequence of vertices. In order to check if this solution is correct, we only need to check if those vertices actually form a Hamiltonian path. Evidently, P ⊆ NP , since a solution can be verified in polynomial time by simply solving the problem. However, the proof or whether the other inclusion holds or not has not been found, and remains as the most important open problem in computer science. The vast majority of complexity theorists believe P ̸= NP , since the equality would imply that the class of the most difficult problems in NP , called NP-complete, would also be equal to P, i.e, solvable in polynomial time. To define this class, let’s introduce some concepts first. Definition 2.1.5 (Reduction, NP-Hard). A decision problem A is polynomial-time re- ducible to another decision problem B, noted A ⩽p B, if there exists a polynomial-time computable function γ such that x ∈ A if and only if γ(x) ∈ B. A problem B is NP-hard if A ⩽p B for every A ∈ NP , i.e, every problem in NP can be polynomial-time reducible to it. 6 Chapter 2. State of the art We are now in position to define NP-completeness. Definition 2.1.6 (NP-complete). A decision problem is NP-complete if it is NP-hard and it belongs to NP. As we were mentioning, an NP-complete problem has a polynomial-time algorithm that solves it if and only if P = NP , and this would revolutionize the world as we know it. Not only in the field of Computational Complexity, but also any field that relies on the assumption that some problems are computationally hard, such as Cryptography, Artificial Intelligence or even Finance. This is why an obvious way to tackle this problem is to show that a problem known to be NP-complete does not belong to P. This could be done in different ways, but in this text we will focus in one in particular: through the study of Boolean circuits. 2.2. Techniques to solve P vs NP In the past, various approaches have been employed in attempts to solve the famous P vs NP problem. Here are some notable ones: Proof techniques: Researchers have explored different proof techniques such as di- agonalization reduction, and contradiction to establish results related to P vs NP. Complexity classes: The study of various complexity classes, such as NP-complete problems, has played a crucial role in understanding the P vs NP problem. Re- searchers have focused on the structure and relationships between different com- plexity classes to gain insights into the nature of the problem. Oracle machines: Researchers have studied the power of hypothetical machines with access to an oracle for solving specific problems efficiently. By analyzing the limita- tions of such machines, they have attempted to shed light on the P vs NP problem. Approximation algorithms: Another approach has been to investigate the possi- bility of efficiently approximating NP-hard problems. Researchers have developed approximation algorithms that provide near-optimal solutions for certain problem instances, but not in a provably optimal manner. Structural properties: Exploring the structural properties of problems and the ex- istence of efficient algorithms for specific problem classes has been another avenue of research. Circuit complexity: Techniques from circuit complexity theory have been em- ployed to analyze the computational power of Boolean circuits and their relationship to P and NP. 2.3. Circuit complexity 7 The most common technique in the last 50 years has been diagonalization, which originates from Cantor’s proof in 1891 and was later used by Turing to demonstrate the undecid- ability of the Halting problem. However, this proof technique alone is not sufficient to show that P ̸= NP , as demonstrated by Baker, Gill, and Solovay [BGS75]. The problem with this technique is that it treats problem-solving machines as black boxes. The important aspect is to analyze what is happening at a local level. For this reason, we decided to focus on the study of Boolean circuits. 2.3. Circuit complexity The purpose of the study of Circuit Complexity is to understand and measure the reasons why the minimum circuit that computes a Boolean function is either big or not in relation to the size of its input. To understand this statement, and explain why it is helpful to determine whether P is equal or not to NP, we have to introduce some concepts. First of all, let’s introduce and alternative way to represent decision problems, based on Boolean functions. Definition 2.3.1 (Boolean function). A Boolean function is defined as f : Z∗ 2 −→ Z2, i.e, a function that takes a binary input of any size and returns either 1 or 0. In particular, if the input size is n, we will denote it as fn : Zn 2 −→ Z2. Then, we can identify a Boolean function f with the set Lf = {x : f(x) = 1}, which defines a decision problem. When there is no ambiguity with f we will just write L. During this text, we will express such languages as L = {x ∈ Zn 2 : fn(x) = 1}n⩾1 since we will study the decision problem for certain sizes n of the input. We need to establish a certain relation between decision problems and Circuit Complexity, but first we need to define the concept of Boolean circuit. Definition 2.3.2 (Boolean circuit). A Boolean circuit C of n ∈ N inputs is a directed acyclic graph in which n nodes are sources and m are sinks, and the nodes in between are logical gates. The size of a circuit is the number of logical gates it contains. Given x ∈ Zn 2 , we denote the output of the circuit as C(x) ∈ Zm 2 . From now on, we will consider Boolean circuits with m = 1 and fan-in 2, i.e, every gate has 2 inputs at most. A circuit C of size n computes a Boolean function f : Zn 2 −→ Z2 if for every x ∈ Zn 2 , C(x) = f(x). Example 2.3.1. Let’s consider the following circuit, 8 Chapter 2. State of the art x1 x2 x3 which can be expressed as C(x) = (x1 ∨ x2) ∧ x3 and has the associated truth table x1 1 0 1 0 1 0 1 0 x2 1 1 0 0 1 1 0 0 x3 1 1 1 1 0 0 0 0 C(x) 1 1 1 0 0 0 0 0 This circuit computes the function f : Z3 2 −→ Z2 such that f((1,1,1)) = 1, f((0,1,1)) = 1,..., f((0,0,0)) = 0. Observation 2.3.1. A function can be computed by multiple circuits, so normally when we mention "the circuit that computes it" we will mean the minimum (one among the ones with the least size). We are now in position to understand how Boolean circuits and complexity of decision problems are connected. With this aim, a complexity class that contains the decision problems that can be computed by small circuits was created. Let’s formalize this concept. Definition 2.3.3 (P/poly class). A decision problem A ≡ {x : fn(x) = 1, fn : Zn 2 −→ Z2}n⩾1 belongs to P/poly if there exists a family of circuits {Cn}n⩾1, each of polynomial size with respect to n, such that Cn computes fn for every n. Note that, for the same decision problem, the circuit that computes the function can be completely different for each size of input (the only requirement is for its size to be polynomial with respect to it). As proved in [AB09], P ⊆ P/poly. However, the other inclusion does not hold since P/poly even contains undecidable languages, such as recognizing the set of unary codes in {1}∗ representing a Turing machine not accepting its own code. This is why by proving NP ̸⊆ P/poly we would prove P ̸= NP . In order to show this, if is sufficient to find a decision problem A such that A ∈ NP but A ̸∈ P/poly (we will refer to this as finding superpolynomial lower bounds), since this would imply A ̸∈ P . So, why is this approach reasonable? First of all, let’s introduce an interesting result. 2.3. Circuit complexity 9 Theorem 2.3.1. [Sha49] For n ⩾ 100, almost all Boolean functions f : Zn 2 −→ Z2 require a circuit of size at least 2n 10n to be computed. Based on this result, the majority of functions require superpolynomial circuits. Finding just one of these functions and proving the corresponding decision problem belongs to NP would be sufficient to show P ̸= NP . Moreover, the study of circuits gives an insight of why things occur the way they do. Instead of treating it as a black box, we could understand and identify certain behaviors and characteristics that contribute to the size of a circuit. There are some interesting results regarding circuit complexity, such as an exponential lower bound for monotone circuits — circuits with only OR and AND gates — computing the CLIQUE decision problem [RW93]. However, circuit complexity remains a highly open field. For instance, it is even an open problem to find a function in the complexity class NEXP — decision problems that can be solved by a non-deterministic Turing machine within exponential time — that it is not in P/poly! Progress on general circuits has been almost nonexistent: a lower bound of n is trivial for any function that depends on all its input bits. The best circuit lower bound we can do after years is 5n− o(n) for any NP problem [AB09]. Chapter 3 Presentation of the new approach In this chapter we will present the conjecture from which we start in order to tackle the problem P ̸= NP. The hypothesis is briefly explained in the first section. In the second section, we present some decision problems that are fundamental in complexity theory in order to test whether the conjecture seems true or not. Finally, in the last section we present the experiments we have carried out to give further support to the proposed conjecture. 3.1. Equanimity and entanglement Our approach to face the P ̸= NP problem will be based on the general observation that functions requiring big circuits to be computed fulfill some properties, as well as some intuitive arguments explaining why small circuits should not be able to compute functions following these properties. In particular, we will construct two concepts that together can empirically separate func- tions computed by big circuits from those with small ones. Our goal is to give a new angle to face this millennial quest supporting the conjecture with experimental results. First, we start with the concept of equanimity, attempting to formalize the opposite of privileging some inputs over others, a property that is inherent in polynomial-sized circuits. Note that a polynomial-sized circuit cannot replicate what it locally does to some subset of the input bits to all the other subsets, because the number of gates would grow combinatorially. Hence, these circuits must privilege some combinations of bits over the others in the way gates treat them. In order to measure this property on functions, we defined two different approaches that are different from each other but try to capture the same thing: when a function is equanimous. However, there is a counter example to this intuition, the PARITY problem, a problem in P/poly which is very equanimous, showing the need to introduce a new 10 3.2. Decision problems of interest 11 concept, entanglement. Secondly, we present the entanglement concept as a way to try to separate every NP problem which is equanimous from the factors that make PARITY equanimous. This is, although PARITY is very equanimous, all the inputs of the optimal polynomial-sized circuit that computes it are only directly affecting a small region of that circuit. We suspect this is exactly what lets PARITY be computed by a small circuit despite its high equanimity. However, if we demand the opposite, namely that the function entangles its inputs and still maintains equanimity, then we suspect this function will require a big, ideally super polynomial, circuit to be computed. To sum up, our conjecture states that every function that is equanimous and entangled can only be computed by circuits of super polynomial size (i.e., it cannot belong to P/poly). We believe that a super polynomial lower bound could be obtained for circuits that satisfy certain equanimity and entanglement criteria. In this scenario, P ̸= NP would be immediately proved by finding an NP-Complete problem that satisfies these conditions (since, as demonstrated earlier, P ⊂ P/poly). In fact, we have found a problem that we will define later, which is NP-complete and seems to be very equanimous and entangled: CLIQUE′. Observation 3.1.1. A natural proof is one that shows the circuit size of any sequence of functions that satisfy certain natural property is superpolynomial. In order to be natural, a property must satisfy two conditions: it can be computable in time that is polynomial in the truth table of fn 1 (constructivity) and it is satisfied by a sufficiently large fraction of the set of all Boolean function (largeness). As shown by Razborov [RR94], no strategy along these lines can ever succeed to prove P ̸= NP . Such a proof would imply the existence of an algorithm capable of breaking a pseudorandom generator (essential in Cryptography), which is widely believed to be impossible. As we will show during the following chapters, our metrics satisfy the constructivity con- dition. However, being both highly equanimous and entangled at the same time is feasible for a small amount of functions, so we do not expect our criterion to satisfy the largeness condition and the property would not be natural. 3.2. Decision problems of interest In order to test the metrics described in the following sections and check if these definitions are able to capture the desired behavior, we have chosen some functions with instructive properties. These functions will be used to compare their metric values with those of a 1Note that the size of the truth table of a Boolean function is exponential with the number of input variables 12 Chapter 3. Presentation of the new approach larger set of functions at a later stage. 3.2.1. Problems known to be in P/poly A problem usually studied in complexity theory is the language PARITY because it has an unusual property: it has a small circuit although it has the most complex DNF (Disjunctive Normal Form) and CNF (Conjunctive Normal Form). Definition 3.2.1 (PARITY Problem). Given a binary input, it determines whether the number of ones is even or not. It can be represented as the family of functions {pn : n ∈ N}, where pn : Zn 2 −→ Z2 (x1, ..., xn) 7→ |{i : xi = 1, 1 ⩽ i ⩽ n}| = 0 (mod 2) The n-variable PARITY function and its negation are the only Boolean functions for which all disjunctive normal forms have the maximal number of 2n−1 monomials of length n and all conjunctive normal forms have the maximal number of 2n−1 clauses of length n. The reason why this is happening is for the hypercube representation in the Karnaugh procedure. 1 0 0 1 0 1 1 0 That is, each vertex is connected to others that have the opposite value, so that when applying the Karnaugh map algorithm, the most complex DNF and CNF possible is obtained. In fact, from the Håstad’s Switching Lemma [Hå14], PARITY /∈ AC0, which means it cannot by computed by a polynomial-sized, constant-depth circuit with AND, OR and NOT gates of unbounded fan-in. From this point of view, PARITY may seem very complex; however, PARITY is in P , and there is a simple circuit that computes it2. Because of this, if our metrics didn’t reflect PARITY function’s simplicity, they would not be adequate. In order to prove this result, Håstad’s introduced a certain form of expressing Boolean circuits, called Alternating Circuit (AC) Form. This form is useful since it is easier to 2pn(x) = x1 ⊕ x2 ⊕ ...⊕ xn, where ⊕ denotes the exclusive or (XOR). 3.2. Decision problems of interest 13 visualize and to understand, and we will use it to explain some concepts and to carry out experiments. Definition 3.2.2 (AC form). A Boolean circuit has AC form if: Level 0 is composed solely of the NOT gate and the identity Inputs of gates in level i > 0 come from level i-1 The depth (d) — which is the number of levels — is odd Gates at level i > 0 function as AND gates when i is odd, and as OR gates otherwise. Observation 3.2.1. If a Boolean function of n inputs can be computed by a circuit C with size s(n) and depth d(n), it can be demonstrated that the same function can also be computed by a circuit C ′ in AC form. The size and depth of C ′ can be obtained by polynomial transformations of s(n) and d(n). The problem of finding whether a number is prime or not has been around for a long time. It was suspected to be in the NP-Intermediate class of decision problems — neither in the class P nor NP-complete but still in NP. However, in 2002, it was proven that it’s a problem in P by the AKS polynomial decision method, created from the Number Theory field in Mathematics. Let’s enunciate this problem for a binary input: Definition 3.2.3 (PRIMALITY Problem). Given a binary input, it determines if the corresponding number is prime or not. It can be represented as the family of functions {Pn : n ∈ N}, where Pn : Zn 2 −→ Z2 (x1, ..., xn) 7→ y is prime, where y = ∑n i=1 xi ∗ 2i−1 Since this problem is in P, our metrics should classify it as “simple.” Note that our metrics consider the best known algorithm, so they could be helpful to determine if problems formerly thought to be NP-intermediate, but being in P, are properly classified by our metrics. Another interesting problem that is in P is the MAJORITY decision problem. Let’s define this problem. Notation 3.2.1. Given x⃗ ∈ Zn 2 , we denote ones(x⃗) = |{i : 1 ⩽ i ⩽ n, x⃗i = 1}|. Definition 3.2.4 (MAJORITY Problem). Given a binary input, it determines if the number of ones is greater than or equal to the number of zeros. It can be represented as the family of functions {Mn : n ∈ N}, where Mn : Zn 2 −→ Z2 x⃗ 7→ ones(x⃗) ⩾ ⌈ n 2 ⌉ 14 Chapter 3. Presentation of the new approach Intuitively, every circuit that computes this function must be somehow biased, given that when the number of ones is already greater than or equal to ⌈ n 2 ⌉ , the information provided by the rest of the inputs is irrelevant. Hence, the function propensity to return 1 is heavily lowered (or raised) when it is conditioned to some known input bits. An objective that aims to avoid our metrics is to make them capable of distinguishing when a problem depends on “what” rather than “how many.” MAJORITY is a clear example of a problem that, similar to PARITY, depends solely on “how many.” 3.2.2. CLIQUE Decision Problems Once we have seen how the metrics behave with problems from the P/poly class, we want to find an NP-complete problem that exhibits high values of equanimity and entanglement, since, if the conjecture were true, this problem would not be in P/poly. If we want a problem whose value depends on “what” rather than “how many”, then the CLIQUE problem is indeed a suitable example. In the CLIQUE problem, each input con- tributes valuable information to the rest, and it is virtually impossible to find a subset of input bits having a trivial dependence on the remaining bits. This characteristic suggests that the CLIQUE function is highly entangled. Besides, since CLIQUE is isomorphism- equivalent, its fairness (i.e., equanimity) should be relatively high. A well-known NP-complete problem easy to implement as a binary function is the Half CLIQUE Problem. In order to define it, we need to see first what a CLIQUE of size k ∈ N is. Definition 3.2.5 (k-CLIQUE). Let G = (V,E) be an undirected graph, where V is the set of vertices and E is the set of edges between those vertices, and let k ∈ N. A k-CLIQUE is a subgraph S = (V ′, E ′) with |V ′| = k such that S is complete, i.e., each pair of vertices u, v ∈ V ′ are connected by an edge (u, v) ∈ E ′. As we know, to show that a problem is NP-hard, we need to see if an NP-hard problem can be reduced in polynomial time to it. Naturally, we will choose the CLIQUE Decision Problem, which we know is NP-complete. Definition 3.2.6 (CLIQUE Decision Problem). Given an undirected graph G = (V,E) and k ∈ N, the problem consists in deciding whether G contains a k-CLIQUE or not. We are now in the position to define the Half CLIQUE Problem and to show it is an NP-complete problem. Definition 3.2.7 (Half CLIQUE Problem). Particular case of CLIQUE Decision Problem where k = |V | 2 . Lemma 3.2.1. Half CLIQUE is NP-Complete. 3.2. Decision problems of interest 15 Proof: A problem is NP-Complete if and only if it is in NP and it is NP-Hard. Therefore, the proof for the statement consists of two parts: Half CLIQUE is in NP. Given a subset V ′ of vertices as a possible solution of the problem, we can validate this solution by verifying if all vertices of V ′ share an edge with each other. This can be done in O(V + E), thus polynomial. Half CLIQUE is NP Hard. Let´s show the CLIQUE problem can be reduced to the Half CLIQUE problem. We consider an instance of the clique problem, being G = (V,E) an undirected graph and k ∈ N, and we convert it into G′ = (V ′, E ′) to be the instance of the Half clique problem. There are two scenarios to be considered: k ⩾ |V | 2 . Let’s take V ′ = V ∪ I and E ′ = E, where I is a set of vertices each of degree 0. We can take |I| = 2k − |V | to ensure k = |V ′| 2 . Therefore, G has a clique of size k if and only if G′ has a clique of size k. k < |V | 2 . Let’s take V ′ = V ∪M and E ′ = E ∪F , where M is a set of vertices which are connected to every other vertex in V ′ by edges in F . We pick |M | such that |M | = |V | − 2k, so k′ := k + |M | = |V ′| 2 . Therefore, G has a clique of size k if and only if G′ has a clique of size k′. Since the Half CLIQUE problem is computationally easier, we will use it for our experi- ments. From now on, when we mention the CLIQUE in the context of our experiments, we will be referring to the Half CLIQUE problem. Let’s define it given a binary input. Definition 3.2.8 (CLIQUE Problem). Given a binary input representing the edges of an undirected acyclic graph, it returns 1 if that graph contains a Half Clique. We will denote the family of functions as {Cn : n ∈ N}. However, through the experiments we will introduce in Chapter 6, we observed that the previous problem was not very unbiased (i.e., equanimous). This does not contradict our conjecture, as a function requiring super-polynomial circuit does not need to be equani- mous and entangled (the implication of the conjecture does not go this way). The goal is to find a NP-complete problem which has high values for both metrics, and therefore, if the conjecture were really true, it would necessarily require a super polynomial circuit to be computed. What is wrong about the Half CLIQUE Problem is its equanimity. Therefore, since PARITY is highly even, we decided to define a new problem CLIQUE′, which combines both Half CLIQUE and PARITY decision problems. Definition 3.2.9 (CLIQUE′ Decision Problem). Input: Undirected graph G = (V,E). 16 Chapter 3. Presentation of the new approach Output: Reply yes if and only if: i. G contains a CLIQUE of size |V | 2 and |E| is even. ii. G doesn’t contain a CLIQUE of size |V | 2 and |E| is odd. Similar to the definition of the CLIQUE Problem, we identify as {C ′ n : n ∈ N} the family of functions that receive a binary input of size n and return the output of the CLIQUE′ decision problem. As we will see later, very high values are obtained in both metrics by this problem. Let’s see it is a NP-complete problem. Theorem 3.2.1. CLIQUE′ is NP-Complete Proof: We check both conditions for NP-Completeness. CLIQUE′ is in NP Certificate: Let S = (V ′, E ′) be a subgraph of G = (V,E). Note that the construction of a certificate S only needs to define a subset of V , V ′, which can be done in non-deterministic polynomial time. Validate: To verify the correctness of the certificate, we need to validate the following predicates first: 1. C := S is a complete subgraph with |V ′| = |V | 2 ⇐⇒ ∀(u, v) ∈ V ′, (u, v) ∈ E ′∧|V ′| = |V | 2 ⇐⇒ (u, v) ∈ V ′, G[u][v] = 1 (if G is implemented with an adjacency matrix) ∧|V ′| = |V | 2 . This can be done in time O(|V ′|2) = O(( |V | 2 )2). 2. P := |E| is even ⇐⇒ P = 0 mod 2. This can be tested in constant time. The certificate is correct if and only if (P ∧ C) ∨ (¬P ∨ ¬C). As a summary, we have obtained a non-deterministic polynomial algorithm that solves the problem and therefore CLIQUE′ is in NP. CLIQUE′ is NP-Hard if every algorithm in NP can be reduced in polynomial time to CLIQUE′. As it was seen in Lemma 3.2.1, the Half CLIQUE Problem is NP-Hard, therefore every problem in NP can be reduced to the Half CLIQUE Problem in polynomial time. Thus, if the Half CLIQUE Problem is reducible in polynomial time to CLIQUE′, then every NP Problem can be reduced to CLIQUE′ in polynomial time. It can be shown that the latter is true. We will present a polynomial-time Turing reduction between these problems (alternatively, a many-one polynomial-time reduction could also be constructed, in particular by adding 3.3. Experiments to support the conjecture 17 two nodes isolated from the rest but connected with each other with an edge when |E| is odd). Using the same notation for P as before, let H be the true/false answer of the Half CLIQUE Problem for G = (V,E), it can be shown with first-order logic that P NXOR CLIQUE ′ ≡ H: ¬(P ⊕ CLIQUE ′) ≡ (P ∧ CLIQUE ′) ∨ (¬P ∧ ¬CLIQUE ′) ≡ (P ∧ ((H ∧ P ) ∨ (¬H ∧ ¬P ))) ∨ (¬P ∧ ¬((H ∧ P ) ∨ (¬H ∧ ¬P ))) ≡ (P ∧H) ∨ (¬P ∧H) ≡ (P ∨ ¬P ) ∧H ≡ ⊤ ∧H ≡ H To sum up, this can be represented with the following scheme: G = (V,E) CLIQUE′ P |E| H That is, the Half CLIQUE Problem can be reduced to CLIQUE′ by testing if the number of vertices is even and with an NXOR gate, therefore, in polynomial time. 3.3. Experiments to support the conjecture The purpose of this section is to simply present all the different experiments that have been carried out with the aim of providing empirical support for the concept. The development and presentation of the results will be explained later on in Chapter 6. The first experiment consists of drawing conclusions about the dataset of José Ramón Cobián [CF23]. This dataset contains exactly the Boolean functions from five bits to one bit which can be computed by circuits of 10 or less NAND gates. We will compare this dataset with a large sample of 5-bit Boolean functions randomly selected, and see 18 Chapter 3. Presentation of the new approach if it is possible to predict whether they will belong to this dataset or not (i.e., whether they can be computed by particularly small circuits). We are interested in obtaining percentiles that completely separate both sets, as these percentiles could provide us with more information about the aforementioned lower bound sought earlier. Secondly, we want to provide more information about these percentiles, since working only with 5-bit Boolean functions, the information obtained from the previous experiment will obviously not be asymptotic, that is, it will not reflect the general tendency as the number of input bits grows. In other words, we want to observe the scalability of the metrics. This experiment consists of taking a small sample of N-bit Boolean functions, which, according to Theorem 2.3.1, are unlikely to belong to P/poly, in order to observe the values of the metrics they possess. Moreover, with this experiment, a more detailed comparison could be provided regarding where the mentioned problems of interest, mentioned in the previous section, are encountered. The last experiment is divided into two parts, studying a particular case of a circuit called “Alternate circuits” (defined in 3.2.2) by requiring that x1 ∧ x2 always appears at the first level, while x3 ∧ x4 never appears, and all circuits have a size limit of 50 gates. In the first part, we observe what happens when we enforce that x1 ∧ x2 only affects one branch of the circuit. The goal is to find functions that are able to be equanimous at least between {x1, x2} and {x3, x4}, i.e., to find functions that have a similar behavior to PARITY. On the other hand, if we “poison” the entire second level with the output of gate x1∧x2, then it is impossible for the function not to be biased in favor of x1∧x2. This supports the conjecture that a function computed by a small and tangled circuit cannot be equanimous. With these experiments, we aim to convince researchers in this field that the conjecture seems to be true, with the hope that someone may use it to finally solve the Millennium Problem. Both the code and the data can be found in the repository [CC23]. Chapter 4 Equanimity 4.1. Introduction to the concept of equanimity It is more than reasonable to think that a Boolean function of polynomial size, by the mere fact of being it, inevitably is biased. This resulted in us having to measure when a Boolean circuit is unbiased, what we called equanimity. Our conjecture states that a problem that is in P/poly should have low values of equanimity for every Boolean function of its family, as every circuit that computes these functions should be biased. A good metaphor of this unbiased situation on a circuit could be to think of a tightrope walker crossing a thin line while holding a pole. All inputs in a circuit should have the same effect on the output of an equanimous circuit, otherwise the output falls into one region of the inputs. A similar thing happens with the tightrope walker: if he does not calibrate the weights on each side of the pole he would fall into one side of the line. In order to visualize this assumption that polynomial circuits bias unavoidably, let’s see the following example. Example 4.1.1. The variable x1 in an unbiased circuit should have an effect on every other variable equally. However, if the input x1 affects only a small region of the circuit, then the effect on the variables that are near it through the evaluation of the circuit is more substantial than the one in further variables. Here we are understanding the concept of distance as the level where both inputs intersect. Note that this phenomenon also depends on the type of gates where the inputs intersect. The goal of an unbiased circuit is to have the ability of balancing the inputs in a way where all of them have the same impact on its final value (that is, whether the output of the circuit is 0 or 1). A simple way to comprehend this abstract concept is by comparing how x1 is “accompa- nied” along the circuit by each different variable as it is shown in the figure below, which 19 20 Chapter 4. Equanimity represents a circuit in AC form (defined in 3.2.2). x1 x2 100% x3 0% x4 0% x5 50% x6 50% x7 50% x8 50% For each wire in a circuit, we can consider the Boolean function it computes. If we see these functions in DNF, then the wires at the bottom compute the trivial DNFs x1, x2, etc. Firstly, the set of conjunctive clauses computed by an AND gate is the Cartesian product of the set of clauses of its inputs (removing all clauses with contradictions, i.e., xi ∧¬xi). Secondly, the set of clauses computed by an OR gate is the union of the sets of its inputs. Since the AND gate in the left is the only gate where x1 AND x2 intersect, this forces x1 to always be accompanied by x2. On the other hand, the OR gate just above has a different behavior, as it forces x1 to never be accompanied by x3 or x4 (the set of clauses in this case is {x1∧x2, x3∧x4}). The other percentages below x5, x6, x7, x8 are reasoned by a similar argument (we just have to see how the Cartesian product applies to the set of clauses received at the top OR gate). As we can see, this behavior, inherent in every polynomial circuit, produces a bias in the function computed by the circuit. For instance, a simple way to balance the difference between x1 and (x3, x4) is by including new AND gates to join the latter inputs, making the number of gates increase. Fixing the bias this way is gates-consuming, and a polynomial-sized circuit cannot afford to include a subcircuit specially dedicated to deal with each possible combination of 2 inputs, 3 inputs, and so on (since the number of subcircuits would not be polynomial). Intuitively, all circuits of polynomial size are condemned to privilege some subsets of inputs over others during their computation. This is why it seems reasonable to see equanimity as a metric that identifies super-polynomial circuits. 4.2. Equanimity based on the importance of each variable 21 Since the property of equanimity must be maintained in all circuits that compute the same function, we should analyze when a Boolean function is unbiased. A Boolean function is biased if its output is strongly determined by a certain subset of the input rather than the others. For example, the Boolean function fn(x) = x2 is biased towards x2, since only those subsets of the input that contain x2 are relevant to the output. On the contrary, a function is unbiased if every combination of the input is relevant to the output. Intuitively, if the number of connections between inputs increases, the number of gates of the Boolean circuit that computes the functions will increase (since “connecting inputs” means linking them with a gate). This is why we theorize the following: “Being unbiased is only within reach of bigger circuits.” During this section, we will formalize this concept in order to measure bias in functions and we will analyze if the previous statement holds or not. There are two different ways of approaching the formalization of this concept, so we will introduce them and explain why both are interesting. 4.2. Equanimity based on the importance of each vari- able In order to be unbiased, all variables in a Boolean function should be considered equally, i.e, every variable is as “important” as the others. Let’s formalize what we mean by important. Definition 4.2.1 (Important variable). Let f : Zn 2 −→ Z2 be a Boolean function. The i− th variable is important to f if and only if ∃ x⃗, y⃗ ∈ Zn 2 : f(x⃗) ̸= f(y⃗), with xi = 1 ∧ yi = 0 ∧ ∀j ̸= i, xj = yj Note that we don’t only have to know whether a variable is important or not, but also in how many combinations it is important. Definition 4.2.2 (Degree of importance). Let f : Zn 2 −→ Z2 be a Boolean function. The degree of importance of the i-th variable, I(i), is the number of different combinations in which the output of f depends on whether xi = 0 or xi = 1. Formally, I(i) := |{(x⃗, y⃗) ∈ Zn 2 × Zn 2 : (xi, yi) = (1, 0) ∧ ∀j ̸= i, xj = yj ∧ f(x⃗) ̸= f(y⃗)}| Note that if I(i) > 0 then the i-th variable is important. Let’s see an example to understand this concept better and to show how to calculate it. 22 Chapter 4. Equanimity Example 4.2.1. Let f3(x) = x1 ∨ x2. This function has the following truth table associ- ated: x1 1 0 1 0 1 0 1 0 x2 1 1 0 0 1 1 0 0 x3 1 1 1 1 0 0 0 0 x1 ∧ x2 1 1 1 0 1 1 1 0 Let’s calculate how many times is each variable important. In order to do this, we have to consider every possible combination of the other inputs, and see how changing the value of the variable affects the output. Let’s begin with the variable x1. If x2 = 1 and x3 = 1, we consider x⃗ = (0, 1, 1) and y⃗ = (1, 1, 1). Since f(x⃗) = f(y⃗), the variable x1 is not important in this context. By the same method, we obtain this variable is only important when x2 = 0 and x3 = 1 and when x2 = 0 and x3 = 0, so I(1) = 2. Symmetrically, I(2) = 2. It is easy to see that the variable x3 is never important, so I(3) = 0. It could be thought it is enough to see if I(i) is similar for every variable i to determine whether a function is biased or not. However, this is not entirely accurate. Example 4.2.2. Let’s consider the Boolean function fn(x) = n−1∧ i=0 xi In this case, I(i) = 1 ∀i ∈ {1, ..., n}. However, this function is totally biased towards the combinations of the input that don’t have a 0 in them, since having a 0 immediately implies the output will be 0. This is why we also have to consider the value of I(i) itself. In short, a function is totally unbiased if every variable is important for every combination, i.e, the sum of the degrees of importance of each variable. Note that our initial conjecture states that all circuits computing functions that have high values of equanimity should be big. If a substantial amount of variables have low degrees of importance, the equanimity will be greatly reduced. All of these reflections lead us to the following definition of the metric. Definition 4.2.3 (Equanimity based on the importance of each variable). Given f : Zn 2 −→ Z2, we define its equanimity as QI(f) = ∑n x=1 I(i) n ∗ 2n−1 The denominator in the expression above is used to normalize the values so Q(f) ∈ [0, 1], where 0 means totally biased and 1 means totally unbiased. 4.3. Equanimity based on the survival of subsets 23 4.2.1. Implementation for QI The following function takes a Boolean function of n input bits fn as an input and returns QI(fn) double equanimity_importance(const vector& f, const int N) { int I = 0; // calculate I(i) for every 1<=i<=n and add it into I for (int i = 1; i <= N; i++) for (int j = 0; j < pow(2, N); j += pow(2, i)) for (int k = 0; k < pow(2, i - 1); k++) if (f[k + j] != f[(k + j) + pow(2, i - 1)]) I++; // return the value of Q_I(f) return (I + 0.0) / (N * pow(2, N - 1)); } The outer loop iterates through every variable, and the inner loops iterate through the truth table associated to fn (which is not explicitly constructed) in order to calculate the number of times the variable is important in determining the function’s output. Since for every variable we have to iterate through the entire truth table (which contains 2n entries), the cost of this algorithm is in O(n · 2n). If we express this in the size of the truth table, the cost is O(log2(N) ·N), where N = 2n. 4.3. Equanimity based on the survival of subsets In the last approach, we described the bias as the difference of importance between vari- ables. Another reasonable consideration would be to define bias as the difference of importance between subsets of the input, but to measure this concept we need to state first what we mean by importance in subsets of the input. Note that the value of each variable could be 0 or 1, therefore subsets of the input are subsets of variables in any possible combination of positive and negative values. Intuitively, a subset of the input is important if its value is reflected in the output of the Boolean function, i.e., its value survives the circuit. Let’s formalize this idea, but first we need to fix some notation. Notation 4.3.1. Let x⃗ := (x1, ..., xn) ∈ Zn 2 be a binary input, and S ⊂ {1, ..., n} be a set of indices that represent a subset of variables, with |S| = k. Then, we denote x⃗S := (xi1 , ..., xik), with {i1, ..., ik} = S. We are now in position to define the survival of subsets. Definition 4.3.1 (Survival of subsets). Given a Boolean function f : Zn 2 −→ Z2 and S be a subset of variables, with |S| = k. Then, we say x⃗S ∈ Zk 2 survives if ∃z⃗ ∈ Zn−k 2 : gx⃗S(z⃗) = 1 24 Chapter 4. Equanimity where gx⃗S : Zn−k 2 −→ Z2 gx⃗S(x⃗S) = f(x⃗) Similarly to the first approach, it would be more informative to know the amount of survival a subset has. Definition 4.3.2 (Degree of survival). Given a Boolean function f : Zn 2 −→ Z2, the amount of times a subset of the input x⃗S survives is denoted by cx⃗S = |{gx⃗S(z⃗) = 1 : z ∈ Zn−k 2 }| This concept may seem a bit confusing, so let’s clarify it with an example. Example 4.3.1. Let f4(x) = (x̄1 ∧ x2) ∨ x4. Its associated truth table is x1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 x2 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 x3 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 x4 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 f4(x) 1 1 1 1 1 1 1 1 0 1 0 0 0 1 0 0 Let’s consider S = {1, 3} and x⃗S = (0, 0), i.e., any input in which x1 = 0 and x3 = 0. This corresponds to the 6th, 8th, 14th and 16th columns of the truth table. As we can observe, gx⃗S((1, 1)) = f((0, 1, 0, 1)) = 1 (6th column), gx⃗S((0, 1)) = f((0, 0, 0, 1)) = 1 (8th column), gx⃗S((1, 0)) = f((0, 1, 0, 0)) = 1 (14th column) and gx⃗S((0, 0)) = f((0, 0, 0, 0)) = 0 (16th column). Therefore, cx⃗S = 3. An equanimous function should treat all subsets equally, therefore the degree of survival should be similar for every subset of the input. However, the amount of survival for a subset is dependent on the size of this subset. For this reason, it is desirable to seek equanimity in subsets of the same size. This led us to use variance to see if all degrees are the same for subsets of the same size. Definition 4.3.3. Let f : Zn 2 −→ Z2 be a Boolean function. We define the average in degree of survival of a given size k as µk = 1 ωk ∑ x⃗S∈Zk 2 S⊂{1,...,n} |S|=k cx⃗S Then, the variance is defined as σk = 1 ωk ∑ x⃗S∈Zk 2 S⊂{1,...,n} |S|=k (cx⃗S − µk) 2 where ωk is the number of subsets of size k of the input. 4.3. Equanimity based on the survival of subsets 25 Note that the input contains negative and non negative variables, but in order to calculate the number of different subsets we need to take into account that a variable and its negation cannot be in the same subset. The following proposition gives a formula to calculate the value of ωk. Proposition 4.3.1. Let k ∈ N, then ωk = 2k · ( n k ) . Proof: Note that ωk can be expressed as the cardinal of the different binary strings for each subset of the input of size k, i.e., ωk := |{x⃗S : S ⊂ {1, ..., n}, |S| = k}| = |Zk 2 × {S ⊂ {1, ..., n}, |S| = k}| Since the cardinal of the Cartesian product is the product of the cardinals, ωk := |Zk 2| · |{S ⊂ {1, ..., n}, |S| = k}| = 2k · ( n k ) Since we are considering high values of equanimity should imply low bias, this approach should multiply by (−1) the sum of all σk, because high values of σk capture high bias. With all this, we can now formally define this approach of equanimity. Definition 4.3.4 (Equanimity based on the survival of subsets). Given a Boolean func- tion f : Zn 2 −→ Z2, we define its equanimity as QS(f) = − n∑ k=1 σk Note that high values of equanimity, i.e, values close to 0, imply f is unbiased. 4.3.1. Alternative to the definition Let us take into account the following result regarding the range of ωk. Proposition 4.3.1.1. Let k ∈ N, then 0 ⩽ ωk ⩽ 22(n−k−1). Proof. Let S ⊂ {1, ..., n}, |S| = k, then ∀ x⃗S ∈ Zn−k 2 , 0 ⩽ cx⃗S ⩽ |Zn−k 2 | = 2n−k. If we denote m = 0 M = 2n−k By Popoviciu’s inequality on variances [Po35], ω ⩽ ( M −m 2 )2 = ( 2n−k 2 )2 = 22(n−k−1) 26 Chapter 4. Equanimity We can see that if k < k′ then the value of equanimity depends more on σk than σk′ . To solve this issue we could resize the range of values in every σk so that they are in the same scale of [0, 1]. Once every σk is resized into values of [0, 1], the sum of all these σk will be in [0, n], where n is the size of the binary input. If we multiply this value by 1 n then the value will be in [0, 1]. Arguing in the same way so that high values of the metric lead to high values of equanimity, the last thing we have left to do is subtract 1 minus this. This will result in the following metric of equanimity. Definition 4.3.5. (Equanimity based on the survival of subsets normalized) Given a Boolean function f : Zn 2 −→ Z2, we define its equanimity as Q′ S(f) = 1− 1 n n∑ k=1 σk 22(n−k−1) ∈ [0, 1] where Q′ S(f) = 0 means totally biased and QS(f) = 1 means totally unbiased. Although this is an alternative, it does not mean it is a better approach, we will compare all of them later. 4.3.2. Implementation for QS The principal part of the algorithm that receives fn as an input and returns QS(fn) is the one that calculates cx⃗S . In order to do so, we create a data structure called counters which links each x⃗S with its associated cx⃗S . The algorithm will consist on iterating through the truth table of fn and, if the output is 1, the counter value of every subset of that entry will be updated. The following function (in which x represents the entry of the truth table) is the one responsible for this: using counters = unordered_map, int, hash_fn>; void update_counters(vector& count, vector & subset, vector& x, int index) { // Update the counter of the corresponding subset count[subset.size()][subset]++; // Loop to create every subset of x for (int i = index; i < x.size(); i++) { // include x[i] in subset. subset.push_back(x[i]); // move onto the next element. update_counters(count, subset, x, i + 1); 4.4. Limits of equanimity 27 // exclude x[i] from subset and triggers // backtracking. subset.pop_back(); } } As the reader may have noticed, the counters are organized by size to make it simpler to calculate each σk. In the worst case scenario (fn(x) = 1 ∀x ∈ Zn 2 ), the function update_counters is called 2n times, once for each entry of the truth table. Since that function goes through every subset of a set of size n, the total cost of the algorithm is in O(22n) (note that calculating the average and the variance does not add additional cost). This time complexity is quadratic in the size of the truth table of fn. 4.4. Limits of equanimity In this chapter, we have built an intuition on why the circuit that computes an unbiased function must be big. This intuition will be confirmed in Chapter 6. However, although this is true most of the time, there exists a major counter example: the PARITY decision problem. This function fits with the definition of unbiased because every bit in the binary input always has to be taken into consideration. This implies that the function does not bias any region of the input over another. However, as we mentioned in Chapter 3 PARITY is in P/poly. This intuition should be captured in both approaches defined in the previous sections. The following result proves that if we take the equanimity based on the importance of variables, PARITY is completely equanimous. This means that PARITY gives the highest degree of importance to every variable. Theorem 4.4.1. ∀n ∈ N, QI(pn) = 1. Proof. Let n ∈ N, it is sufficient to show that for all variables i, I(i) = 2n−1. In this case, QI = ∑n i=0 I(i) n · 2n−1 = n · 2n−1 n · 2n−1 = 1 For simplicity, we denote Y := {(x⃗, y⃗) ∈ Zn 2 × Zn 2 : (xi, yi) = (1, 0) ∧ ∀j ̸= i, xj = yj ∧ pn(x⃗) ̸= pn(y⃗)} Since |Y| = I(i), the statement is equivalent to say that the application Γ : Zn−1 2 −→ Y z⃗ 7→ (x⃗, y⃗) : (xi, yi) = (1, 0) ∧ ∀j ̸= i, xj = yj = zj 28 Chapter 4. Equanimity is bijective. Note that Γ(z⃗) ∈ Y , ∀z⃗ ∈ Zn−1 2 due to the good properties of the PARITY function. Let’s prove this. Let Γ(z⃗) = (x⃗, y⃗), then pn(x⃗) = xi ⊕ pn−1(z⃗) = ¬pn−1(z⃗) ̸= pn−1(z⃗) = yi ⊕ pn−1(z⃗) = pn(y⃗) The only thing left to prove is the bijectivity of gamma. Injective: Let z⃗1, z⃗2 ∈ Zn−1 2 such that (x⃗1, y⃗1) = Γ(z⃗1) = Γ(z⃗2) = (x⃗2, y⃗2). Then, z⃗1 = x⃗1J = x⃗2J = z⃗1 where x⃗J = (x1, ..., xi−1, xi+1, ..., xn). Surjective: Let (x⃗, y⃗) ∈ Y , if we take z⃗ = x⃗J , then by definition, Γ(z⃗) = (x⃗, y⃗). Well-defined: Let z⃗1, z⃗2 ∈ Zn−1 2 such that (x⃗1, y⃗1) = Γ(z⃗1) ̸= Γ(z⃗2) = (x⃗2, y⃗2), then x⃗1 ̸= x⃗2 =⇒ z⃗1 = x⃗1J ̸= x⃗2J = z⃗1 By all this, I(i) = |Y| = |Zn−1 2 | = 2n−1. The other approach also takes into account this consideration. Every subset of the input is treated equally except the ones of maximum size. This is shown in the following result. Theorem 4.4.2. ∀n ∈ N, QS(pn) = −1 4 Proof. It is sufficient to show that σk = { 0, 1 ⩽ k ⩽ n− 1 1 4 , k = n since this implies QS(pn) = − n∑ k=1 σk = 0− σn = −1 4 Therefore, the statement is divided into two parts: σk = 0, ∀ 1 ⩽ k ⩽ n− 1. Let x⃗S ∈ Zk 2, with S ∈ {1, ..., n}, then cx⃗S = |{gx⃗S(z⃗) = 1 : z ∈ Zn−k 2 }| = |{p⌊n 2 ⌋(x⃗S)⊕ p⌈n 2 ⌉(z⃗) = 1 : z ∈ Zn−k 2 }| = |{p⌈n 2 ⌉(z⃗) = 1 : z ∈ Zn−k 2 }| = ωk 2 Since every subset of the input has the same degree of survival, then the variance is 0. 4.4. Limits of equanimity 29 σn = 1 4 . In this case, S = {1, ..., n}, so for all x⃗ ∈ Zn 2 , cx⃗ = |{pn(x⃗) = 1}| ⩽ 1 Therefore, µn = 1 ωn ∑ x⃗S∈Zn 2 S={1,...,n} cx⃗ = 1 ωn ∑ x⃗∈Zn 2 cx⃗ = 1 ωn ∑ x⃗∈Zn 2 pn(x⃗)=1 1 = 1 ωn · ωn 2 = 1 2 Then, the variance results in σn = 1 ωn ∑ x⃗∈Zn 2 (cx⃗ − µn) 2 = 1 ωn ∑ x⃗∈Zn 2 ( 1 2 )2 = ωn · 1 4 ωn = 1 4 Although equanimity is a good indicator to capture the reasons why circuits must be big, it has some troubles with functions that (despite being small) use a certain trick to be equanimous. For this reason, we need a metric that can ignore that trick and, in addition to equanimity, can provide us a circuit lower bound (ideally superpolynomial) for NP-complete problems. This new metric is what we will call entanglement. Chapter 5 Entanglement 5.1. Introduction to the concept of entanglement In physics, quantum entanglement refers to a fundamental phenomenon in quantum me- chanics where two or more particles become correlated in such a way that their individual properties cannot be described independently [Ho09]. Similarly, in our case, it is intuitive to think that the messier a Boolean function is (i.e., if the effect of every input on the output of the function strongly depends on the other inputs) the bigger the circuit that computes it will be since the connection between variables will increase. Note that the entanglement is a property of Boolean functions, not circuits that compute them. However, this metric should capture the behavior of all the circuits that compute a given Boolean function. For instance, a function should be entangled if all levels of all the circuits that compute it look similar to the following structure. p0 p1 p2 p3 p4 p5 p6 p7 p8 That is, in order to compute its function, the circuit needs to directly combine the outputs of the lower level in all possible combinations. Thus, the upper level cannot be split into 30 5.1. Introduction to the concept of entanglement 31 parts depending on (almost) disjoint subsets of outputs of the lower level. If this level cannot be untangled, the number of gates will increase inevitably in quadratic order to the number of outputs from the level below 1. If this keeps happening for k levels, then the size of the circuits will be in the order of O(n2k). Intuitively, the entanglement of the function will be higher if none of its circuits are capable of untangling their levels. If the number of levels needs to be high enough, then, as we have shown, the size of all the circuits that compute the function will be super-polynomial. Our goal is to define a metric that is capable of capturing this behavior, but how can we quantify this phenomenon? An entangled function forces its variables to interact with each other, as it happens with the quantum entanglement we mentioned earlier. Therefore, it is easier to think that a function is entangled if each subset of variables must provide to its complementary a great amount of information in order to compute the function. To understand the last idea, it is shown in the image below a representation of the amount of information partitions of the inputs are transmitting. For instance, the partition in the left, x⃗S1 , needs to communicate k1 bits of information and the partition in the right, x⃗S2 , needs to send k2 bits to compute the value of the function in x⃗, f(x⃗). A function is entangled if k1 and k2 are high. Note that the partition could be any subset of the set of variables, not only by dividing it in half as the diagram may suggest. k1 bits k2 bits x⃗S1 x⃗S2 f(x⃗) = g(x⃗S1 , x⃗S2) The concept is still pretty abstract and some examples can make it easier to comprehend it. Example 5.1.1. The least entangled functions are fn ≡ 1 and fn ≡ 0 because the partition does not need to communicate any kind of information. This is represented in the following figure. 1For n inputs, the next level will need at least ( n 2 ) gates to connect the inputs with each other, and n more gates to connect the inputs with themselves. Note that ( n 2 ) + n ∈ O(n2). 32 Chapter 5. Entanglement 0 bits 0 bits x⃗S1 x⃗S2 1 Example 5.1.2. The PARITY function is one of the least entangled functions after the constant function, as the information needed to be shared between partitions is only one bit, which represents if the number of ones is either even or odd. In the figure, pn denotes the PARITY function for inputs consisting of n bits. p|S1|(x⃗S1) (1 bit) p|S2|(x⃗S2) (1 bit) x⃗S1 x⃗S2 p|S1| ⊕ p|S2| Example 5.1.3. The MAJORITY function, Mn, has a similar behavior as PARITY, the amount of needed shared information is small. In this case, although every input is determinant for the output, the information they provide can be simplified. For instance, may n = 6 and x = (1, 0, 1, 1, 1, 0). We can divide x in half, obtaining x1 = (1, 0, 1) and x2 = (1, 1, 0). The information needed from each xi is just the number of ones, so only logm bits are required, being m the size of xi. If this simplification can be made, then the function will not be very entangled, since the dependence between variables is not that tight. As it is shown in the figure below, each partition needs to transmit the number of ones it has, which is in the worst case log |S|, with S being the partition of variables. When the total number of ones is gathered, ones(x⃗), the value of the function is 1 if and only if ones(x⃗) ⩾ ⌈ n 2 ⌉ . 5.1. Introduction to the concept of entanglement 33 ones(x⃗S1) ∈ O(log |S1|) bits ones(x⃗S2) ∈ O(log |S2|) bits x⃗S1 x⃗S2 ones(x⃗S1) + ones(x⃗S2) ⩾ ⌈ n 2 ⌉ In the examples above, the number of bits required to transmit the information is inde- pendent of the partition chosen. However, in same cases a function may seem entangled when observed through certain partitions and low-entangled when observed through oth- ers. Let’s see an example of this. Example 5.1.4. Let’s consider the language L = {ww} ⊂ Z∗ 2, which can be expressed equivalently as f : Z∗ 2 −→ Z2 such that f(x) = 1 ⇐⇒ x ∈ L. We will consider the functions of a certain size n, and more specifically, those in which n is even (note that if n is odd, L = ∅, so fn would be the constant 0 function). If we consider the partition obtained by dividing the set of variables in half in the specific order in which they appear in the input, i.e., S1 = {1, .., n 2 } and S2 = {n 2 + 1, ..., n}, then every bit is important and has to be transmitted. This happens because the first half of the input has to be exactly the same as the second one, which of course means every bit has to be the same, so no simplification can be made. However, we can make the partition in a more clever way. Let us see our input x ∈ Zn 2 as x = w1w2, with wi ∈ Z n 2 2 and wi = w1 iw 2 i , where wj i ∈ Z n 4 2 . Let’s take the subset S1 such that w1 1 and w1 2 belong to it, and S2 its complementary. Since w1 = w2 ⇐⇒ wi 1 = wi 2 for i ∈ {1, 2}, S1 only needs to transmit one bit to S2 which indicates whether w1 1 = w1 2 or not (and the same happens from S2 to S1). Following these intuitions, we can understand the entanglement of a Boolean circuit as its internal ability to simplify information in order to obtain the desired output. In our experiments we will show how this data simplification is directly related to a reduction in the number of gates needed to compute the function with a circuit. 34 Chapter 5. Entanglement 5.2. Entanglement formal definition From here on, this abstract concept will be formalized in order to create a metric. For this purpose, we will once again use Notation 4.3.1. We can now define what is a partition of input variables. Definition 5.2.1 (Partition of variables). Let V := {1, ..., n} be the set of variables and S ⊂ V, then {S, V \S} represents a partition of input variables. For simplicity of notation, we refer to V \ S as S unless otherwise mentioned. We need to measure the amount of information needed to be transmitted in the partition before defining the metric. A simple manner to do so is counting the number of different functions obtained by fixing the values of one of the subsets in the partition. This can be formally defined as follows. Definition 5.2.2 (Information shared by a subset). Let f : Zn 2 −→ Z2 be a Boolean function and {S, S} be a partition of variables, where |S| = k. The information that the partition S gives to its complementary is i(S) = |{gx⃗S : x⃗S ∈ Zk 2}| where gx⃗S : Zn−k 2 −→ Z2 gx⃗S(x⃗S) = f(x⃗) Then, an early definition of entanglement could be the following. Definition 5.2.3 (First definition of entanglement). Given a Boolean function f : Zn 2 −→ Z2, we define the entanglement of f as the minimum of the information shared in the different partitions, i.e., T (f) = min{i(S) + i(S) : S ⊂ {1, ..., n}} However, we need to restrict the size of the partition S since otherwise we would get a short range of entanglement values, as it can be seen in the following result. Lemma 5.2.1. Given f : Zn 2 −→ Z2, for S ⊂ {1, ..., n} of any size, i(S) ⩽ min(2|S|, 22 |S| ). Proof: For each possible assignment of values to all variables in S, at most one additional g function is included in the count, so we can obtain no more than 2|S| different g functions. Also, since g functions depend on |S| bits, there can be no more than 22 |S| of them. A problem arises when S is too small (or too big), because the maximum value of i(S) + i(S) would be small compared to other partitions. Since the entanglement is calculated as the minimum of the information shared, these partitions would lower its value just because of their size, making this metric less useful. We are finally in the position to give a proper definition of entanglement. 5.2. Entanglement formal definition 35 Definition 5.2.4 (Entanglement). Given a Boolean function f : Zn 2 −→ Z2, we define the entanglement of f as the minimum of the information shared in the different half-sized partitions, i.e., T (f) = min{i(S) + i(S) : S ⊂ {1, ..., n}, |S| = ⌊ n 2 ⌋ } With this formal definition we are now in the position to show that PARITY has a low entanglement value. Theorem 5.2.1. ∀n ∈ N, T (pn) = 4. Proof: Let’s show i(S) = 2 for any S we choose. In order to do that, we need to prove the following statements first: i ∃z0 ∈ Z⌈ n 2 ⌉ 2 : gx⃗S(z0) = gy⃗S(z0) ⇒ ∀z ∈ Z⌈ n 2 ⌉ 2 , gx⃗S(z) = gy⃗S(z) ii ∃z0 ∈ Z⌈ n 2 ⌉ 2 : gx⃗S(z0) = ¬gy⃗S(z0) ⇒ ∀z ∈ Z⌈ n 2 ⌉ 2 , gx⃗S(z) = ¬gy⃗S(z) We will prove the first statement (the second one is analogous). We can express gx⃗S as gx⃗S(z) = pn(x⃗) = x1 ⊕ x2 ⊕ ...⊕ xn = p⌊n 2 ⌋(x⃗S)⊕ p⌈n 2 ⌉(z) and since gx⃗S(z0) = gy⃗S(z0), we have p⌊n 2 ⌋(x⃗S)⊕ p⌈n 2 ⌉(z0) = p⌊n 2 ⌋(y⃗S)⊕ p⌈n 2 ⌉(z0) so 2 p⌊n 2 ⌋(x⃗S) = p⌊n 2 ⌋(y⃗S) We can conclude, ∀z ∈ Z⌈ n 2 ⌉ 2 , gx⃗S(z) = p⌊n 2 ⌋(x⃗S)⊕ p⌈n 2 ⌉(z) = p⌊n 2 ⌋(y⃗S)⊕ p⌈n 2 ⌉(z) = gy⃗S(z) Therefore, for each partition there are only two different functions, i.e., ∀S, i(S) = 2. Similarly, it can be shown that the MAJORITY function has low entanglement values. Theorem 5.2.2. ∀n ∈ N, T (Mn) = ⌈ n 2 ⌉ + 1 + ⌊ n 2 ⌋ + 1 Proof: Let S ⊂ {1, ..., n}. By the definition of the majority problem, we know gx⃗S(z) = Mn(x⃗) = 1 ⇔ ones(x⃗) ⩾ ⌈n 2 ⌉ ⇔ ones(x⃗S) + ones(z) ⩾ ⌈n 2 ⌉ In order to obtain the value of the entanglement, we will prove first the following state- ments: 2Note that the XOR function satisfies a⊕ c = b⊕ c ⇐⇒ a = b, ∀a, b, c ∈ Z2. 36 Chapter 5. Entanglement ones(x⃗S) = ones(y⃗S) ⇒ ∀z ∈ Z⌈ n 2 ⌉ 2 , gx⃗S(z) = gy⃗S(z) ones(x⃗S) ̸= ones(y⃗S) ⇒ ∃z0 ∈ Z⌈ n 2 ⌉ 2 , gx⃗S(z0) ̸= gy⃗S(z0) The first one is immediate. Let x⃗S, y⃗S ∈ Z ⌊n 2 ⌋ 2 such that ones(x⃗S) = ones(y⃗S). Then, for z ∈ Z⌈ n 2 ⌉ 2 , gx⃗S(z) = 1 ⇔ ones(x⃗S) + ones(z) ⩾ ⌈n 2 ⌉ ⇔ ones(y⃗S) + ones(z) ⩾ ⌈n 2 ⌉ ⇔ gy⃗S(z) = 1 Let’s prove the second one. We can take, w.l.o.g., x⃗S, y⃗S ∈ Z ⌊n 2 ⌋ 2 such that ones(x⃗S) > ones(y⃗S). Let z0 ∈ Z⌈ n 2 ⌉ 2 such that ones(x⃗S) + ones(z0) = ⌈ n 2 ⌉ . Then, ones(y⃗S) + ones(z0) < ones(x⃗S) + ones(z0) = ⌈n 2 ⌉ so gx⃗S(z0) = 1 ̸= 0 = gy⃗S(z0) We have proven the only cases where the gx⃗S functions are different happen when ones(x⃗S) varies. Since |S| = ⌊ n 2 ⌋ , ones(x⃗S) ∈ {0, 1, ..., ⌊ n 2 ⌋ }, so i(S) = ⌊ n 2 ⌋ + 1. By the same argument, i(S̄) = ⌈ n 2 ⌉ + 1. 5.3. Properties of entanglement metric In this section, we will discuss two properties of entanglement that are interesting to consider when working with this metric. As a consequence of Lemma 5.2.1, we can obtain a range of values for the entanglement metric of any arbitrary function f : Zn 2 −→ Z2. To do this, we need to prove the following result. Lemma 5.3.1. Given f : Zn 2 −→ Z2, for S ⊂ {1, ..., n} such that |S| = ⌊ n 2 ⌋ , i(S) ⩽ 2⌊ n 2 ⌋ and i(S) ⩽ 2⌈ n 2 ⌉. Proof: From Lemma 5.2.1, i(S) ⩽ min(2|S|, 22 |S| ), so we have to show 2⌊ n 2 ⌋ ⩽ 22 ⌈n 2 ⌉ for any n ⩾ 1. This is trivially true since ∀n ⩾ 1, ⌊ n 2 ⌋ ⩽ ⌈ n 2 ⌉ < 2⌈ n 2 ⌉. Equivalently, for S, it is sufficient to prove 2⌈ n 2 ⌉ ⩽ 22 ⌊n 2 ⌋ for any n ⩾ 1, which is true since ⌈ n 2 ⌉ ⩽ ⌊ n 2 ⌋ + 1 ⩽ 2⌊ n 2 ⌋. This brings us to the following property of entanglement. 5.3. Properties of entanglement metric 37 Property 5.3.1. Let f : Zn 2 −→ Z2 be a Boolean function, then T (f) ⩽ 2⌊ n 2 ⌋+2⌈ n 2 ⌉. Observation 5.3.1. With this range of values, it can be observed that the entanglement values in PARITY and MAJORITY are quite far from the upper limit, suggesting that they have relatively small values. Another interesting property is that the entanglement of a given function will not increase if we add variables that do not provide information. We use the definition of important variable that we established in Definition 4.2.1 to refer what we mean by variable that provides information. Since we are going to use the set of important variables several times, we fix the following notation. Notation 5.3.1. The subset of variables that are important is denoted by I ⊂ {1, ..., n}. In this way, using the restriction notation that we had established in the previous section, we can define the restriction of a Boolean function, f , to I as the important function of f . Formally, Definition 5.3.1 (Important function). Let f : Zn 2 −→ Z2 be a Boolean function. The function fI : Zm 2 −→ Z2, with m = |I|, is the important function of f if ∀x⃗ ∈ Zn 2 , f(x⃗) = fI(x⃗I). We need to see if this definition is consistent, which is shown in the following result. Proposition 5.3.1. Let X := {f : Zn 2 −→ Z2} and Y := {f : Zm 2 −→ Z2}. The application γ : X −→ Y f 7→ fI is bijective. Therefore, every restriction of γ is also bijective to its image, i.e., if X ′ ⊂ X then, γ|X′ : X ′ −→ γ(X ′) where γ(X ′) = {γ(f) : f ∈ X ′} is also bijective. Proof: Well-defined. If γ(f) for a given f ∈ X has two different images, h1, h2, then there is a z0 ∈ Zm 2 with h1(z0) ̸= h2(z0). Since z0 contains the important part, it can be extended to an arbitrary vector x⃗ ∈ Zn 2 whose restriction to I is z0. Note that for every extension, we obtain the same value for f by definition of I. Therefore, f(x⃗) = fI(x⃗I) = fI(z0) = γ(f)(z0) = h1(z0) ̸= ̸= h2(z0) = γ(f)(z0) = fI(z0) = fI(x⃗I) = f(x⃗) 38 Chapter 5. Entanglement which is a contradiction. Injective. Let f 1, f 2 ∈ X such that f 1 ̸= f 2, i.e, ∃x⃗0 ∈ Zn 2 : f 1(x⃗0) ̸= f 2(x⃗0). Then, γ(f 1)(x⃗0I ) = f 1 I (x⃗0I ) = f 1(x⃗0) ̸= f 2(x⃗0) = f 2 I (x⃗0I ) = γ(f 2)(x⃗0I ). Surjective. Let h ∈ Y . Let’s take f : Zn 2 −→ Z2 such that f(x⃗) = h(x⃗I) ∀x⃗ ∈ Zn 2 . By definition, fI ≡ h, so γ(f) ≡ fI ≡ h. The second statement is immediate. Thanks to the bijection of γ in the previous proposition we can now prove the following property of entanglement. Property 5.3.2. According to the definition of entanglement, let V := {1, ..., n} be the set of variables of a Boolean function f : Z2 n −→ Z2, and I the set of important variables of V. Then, T (f) = min{i(S) + i(V \ S) : S ⊂ V , |S| = ⌊ n 2 ⌋ }. T (fI) = min{i(SI) + i(I \ SI) : SI ⊂ I, |SI | = ⌊m 2 ⌋}, where m = |I|. It is true that T (f) ⩽ T (fI). Proof. To prove this statement, it is enough to show that ∀SI , ∃S : i(S) = i(SI) ∧ i(V \ S) = i(I \ SI), since this would imply ∀SI , ∃S : i(S) + i(V \ S) = i(SI) + i(I \ SI), i.e., {i(SI) + i(I \ SI) : SI ⊂ I, |SI | = ⌊m 2 ⌋} ⊂ {i(S) + i(V \ S) : S ⊂ {1, ..., n}, |S| = ⌊ n 2 ⌋ } showing that T (fI) = min{i(SI) + i(I \ SI) : SI ⊂ I, |SI | = ⌊m 2 ⌋} ⩾ min{i(S) + i(V \ S) : S ⊂ {1, ..., n}, |S| = ⌊n 2 ⌋ } = T (f) Let SI ⊂ I, where |SI | = ⌊m 2 ⌋. We can find a subset S ⊂ {1, ..., n} with the same information by adding non-important variables to SI until |S| = ⌊ n 2 ⌋ . This is, S = SI⊔U ,3 where U ⊂ I. Note that SI ⊂ S ∧ I \ SI ⊂ V \ S, thus showing i(S) = i(SI) is the same as proving i(V \ S) = i(I \ SI). Let’s show the first statement. 3The symbol ⊔ is used to represent disjoint union between sets. 5.3. Properties of entanglement metric 39 It is true that for arbitrary x⃗ ∈ Zn 2 , gx⃗SI (x⃗I\SI ) = fI(x⃗I) (By definition of gx⃗SI ) = f(x⃗) (By definition of fI) = gx⃗S(x⃗V\S) (By definition of gx⃗S) = gx⃗S I ((x⃗V\S)I) (By definition of gx⃗S I ) = gx⃗S I (x⃗I\SI ) (I \ SI contains all the important variables of V \ S) Therefore, gx⃗SI ≡ gx⃗S I . We have proved that, γ({gx⃗S : x⃗S ∈ Z⌊ n 2 ⌋ 2 }) = {gx⃗S I : x⃗SI ∈ Z⌊m 2 ⌋ 2 } = {gx⃗SI : x⃗SI ∈ Z⌊m 2 ⌋ 2 } By Proposition 5.3.1, i(S) = |{gx⃗S : x⃗S ∈ Z⌊ n 2 ⌋ 2 }| = |{gx⃗SI : x⃗SI ∈ Z⌊m 2 ⌋ 2 }| = i(SI), as we wanted to prove. Example 5.3.1. Let’s show a case where T (f) < T (fI) and a practical method to calcu- late the entanglement of a function using its truth table. Let f2(x) = x1 ∧ x2. Its truth table is x1 1 0 1 0 x2 1 1 0 0 x1 ∧ x2 1 0 0 0 In order to calculate the entanglement, we denote S = {1}, so S = {2}. By fixing x1 = 1, we obtain x1 1 1 x2 1 0 g1(x2) 1 0 and by fixing x1 = 0, we obtain x1 0 0 x2 1 0 g0(x2) 0 0 Therefore, since g1(x2) ̸= g0(x2), we have i(S) = 2. By applying the same method, we obtain i(S) = 2, hence T (f2) = 4 (note that switching the roles of S and S does not alter the addition). Let’s now define f4(x) = x1 ∧ x2. Its truth table is 40 Chapter 5. Entanglement x1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 x2 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 x3 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 x4 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 x1 ∧ x2 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 In this case, S could be S1 = {1, 2}, S2 = {1, 3}, or S3 = {1, 4}. Note that, since variables x3 and x4 don’t provide information, if S = S2 or S = S3 then the number of different g functions obtained will be the same as with f = f2 and S = {1}, so i(S2) + i(S2) = i(S3) + i(S3) = 4. Let’s calculate it when S = S1. Since we are fixing x1 and x2, which are the only variables that matter, i(S) =4 |{(x1 ∧ x2) 4 : x1, x2 ∈ Z2}| = 2. For S it happens exactly the opposite, so no matter how we fix x3 and x4, we always obtain g(x3,x4)(x1, x2) = f2(x1, x2), so i(S) = 1. In short, i(S) + i((S)) = 3, so T (f4) = 3. 5.4. Implementation for T In order to obtain the time complexity required to calculate the entanglement value of a function of n input bits, we will present a C++ code of the algorithm and analyze its cost. The main component of calculating the entanglement is determining i(S) for every S, which involves computing the g-functions. The following function, given a subset S ⊂ {1, ..., n} such that |S| = ⌊ n 2 ⌋ (or |S| = ⌈ n 2 ⌉ ) and the truth table of a Boolean function, returns {gx⃗S : x⃗S ∈ Zk 2}. void calculate_g_functions(vector& x, const vector& S, const int pos_s, const bool B, vector& g, unordered_set, hash_fn>& g_set, const int N, const truth_table & TT) { // Base condition if (pos_s < 0) { // S if (B) { vector S_c; complementary_subset(S, S_c, N); vector g; calculate_g_functions(x, S_c, S_c.size() - 1, false, g, g_set, N, TT); g_set.insert(g); } 4For n ∈ N and k ∈ Z2, we denote by (k)n ∈ Zn 2 the element k repeated n times 5.5. Do we still need equanimity? 41 // S_c else { g.push_back(TT.at(x)); } } // Recursive conditions else { x[S[pos_s]] = 1; calculate_g_functions(x, S, pos_s - 1, B, g, g_set, N, TT); x[S[pos_s]] = 0; calculate_g_functions(x, S, pos_s - 1, B, g, g_set, N, TT); } } Since |{x⃗S}| = |Z⌊ n 2 ⌋ 2 | = 2⌊ n 2 ⌋ and for each of them we have to obtain every x⃗S̄ (there are 2⌈ n 2 ⌉ of these) the total cost of obtaining the g-functions belongs to O(2⌊ n 2 ⌋·2⌈ n 2 ⌉) = O(2n). Given that we have to calculate the g-functions for every S (in order to obtain i(S)), and there are ( n ⌊n 2 ⌋ ) different subsets of size ⌊ n 2 ⌋ , the total cost to obtain the entanglement of a Boolean function of n input bits is in O( ( n ⌊n 2 ⌋ ) · 2n) ≡ O(22n), i.e., quadratic on the size of the truth table. 5.5. Do we still need equanimity? We could think that entanglement works well on its own and that equanimity would not be necessary to determine when a function needs to be computed by a superpolynomial circuit. In this section, we are not going to show a counter-example as we did in Section 4.4 for equanimity, but a problem which is in P/poly that apparently has high values of entanglement and low values of equanimity, namely the PRIMALITY decision problem. The problem that PRIMALITY has is that the “what” matters, causing each subset of variables to contribute a great amount of information to its complementary. This would result in a high degree of entanglement. However, if we take into account the prime number theorem (PNT) proved independently by Jacques Hadamard [Had96] and Charles Jean de la Vallée Poussin [VP96] regarding the density of prime numbers, equanimity will decrease as n rises. The prime number theorem describes the asymptotic distribution of the prime numbers among the positive integers, formalizing the intuitive idea that primes become less com- mon as they become larger by precisely quantifying the rate at which this occurs. Because of this behavior of prime numbers, intuitively, the variables with high indices will not be 42 Chapter 5. Entanglement considered equally important to variables with low indices. This is reflected empirically in Chapter 6. Another important consideration to take into account is that entanglement, as we saw in Section ??, is a metric that can be computed in polynomial time with respect to the truth table, thus satisfying the first condition of the natural proof. Therefore, it will be necessary to combine this metric with equanimity to narrow down the set of functions and avoid the second condition of natural proof. Chapter 6 Experimental results 6.1. Performance of metrics in the dataset If we recall our standpoint, we aim to observe that a highly equanimous and entangled function must be computed only by super polynomial Boolean circuits. Therefore, exper- imentally, it should happen that for functions computed by small circuits, low values are obtained for at least one of the metrics. José Ramón Cobián, in his Mathematics bachelor’s thesis [CF23], has programmed a circuit generator that solely employs NAND gates, which we will employ as a reference for functions computed by small circuits. The dataset displays all Boolean functions of 5 bits in one whose minimal circuits of this type have up to 10 gates.1 We will compare these functions with others from a set of equal size2 that are selected in a random manner, making sure they do not belong to the dataset. Firstly, we will present the results of the metrics separately, and later we will examine if the metrics are capable of distinguishing the randomly generated functions from those in the dataset. 6.1.1. Testing the metrics individually The graphs that we will present all share the same structure: Two histograms, one for the functions within the dataset and another for those outside the dataset, are displayed on the same figure corresponding to the respective metric. 1In his unfinished bachelor’s thesis, which he has yet to submit, he demonstrates that all circuits can be transformed into an equivalent one using only NAND gates with a polynomial difference in the number of gates. Therefore, studying this type of circuits does not entail a loss of generality. 2The dataset contains 9,268,995 functions, which is approximately 0.2158% of the total number of different Boolean functions with 5 input bits. 43 44 Chapter 6. Experimental results The x-axis is discretized into intervals representing the metrics values. The y-axis represents the proportion of functions that fall within the corresponding interval, which we will represent with P . We initiate the analysis with equanimity. As discussed in Chapter 4, this metric can po- tentially indicate a larger circuit size. However, there are certain exceptional cases among smaller circuits that leverage unknown techniques to achieve a balanced distribution of their variables, as exemplified by the PARITY function. In Chapter 4, we had defined several approaches to equanimity. Let us first examine the one based on the importance of variables. 0.0 0.2 0.4 0.6 0.8 I 0.00 0.05 0.10 0.15 0.20 Dataset Non dataset From this image, we can observe a quasi-separation between the set of functions within the dataset and those outside of it. Indeed, the intuitions we raised at the beginning of the study are confirmed with this result, as functions outside the dataset exhibit higher values of equanimity than those within. The cases that truly interest us are the extremes, that is, those that are highly equanimous and highly entangled. For the equanimity case, we do not know the exact value that would determine whether a function is equanimous or not. To address this, we consider the 98th percentile, which corresponds to the equanimity value that only 2% of the analyzed functions surpass. We can see below in a green dashed line the value for this threshold. 6.1. Performance of metrics in the dataset 45 0.0 0.2 0.4 0.6 0.8 I 0.00 0.05 0.10 0.15 0.20 98-percentile Dataset Non dataset It can be observed that there is no function in the dataset that surpasses this threshold, which could serve as a bound to determine when a 5-bit function is equanimous. To refine the value of this bound further, one should experiment with n-bit functions and observe their behavior as n rises. That is precisely what we will do in the experiment of the next section. Let’s analyze the results we obtain when examining the other approach to equanimity, con- sidering both its primary version and its normalized version. Our objective is to examine the behavior of subset-based equanimity, its ability to accurately separate datasets, and compare these conclusions with previously discussed approach to equanimity. First, let’s examine the non-normalized version. 46 Chapter 6. Experimental results 20 15 10 5 0 S 0.00 0.01 0.02 0.03 0.04 0.05 98-percentile Dataset Non dataset Despite the fact that the highest values of equanimity are mostly achieved by functions outside the dataset, there are indeed functions within the dataset that exhibit high levels of equanimity. This was already expected, as constant functions are highly equanimous according to this approach. Now let’s analyze the normalized one. 0.4 0.5 0.6 0.7 0.8 0.9 1.0 ´S 0.00 0.01 0.02 0.03 0.04 0.05 0.06 98-percentile Dataset Non dataset Here, it is impossible to determine a clear separation between the dataset and outside the dataset. Perhaps it is more interesting to highlight that the least equanimous functions 6.1. Performance of metrics in the dataset 47 are the small functions, confirming the initial hypothesis that small functions introduce bias. To provide a more numerical result regarding these three versions of equanimity, we calculate which percentage of the functions that exceed the threshold are outside the dataset: For the equanimity based on importance, 99.98 %. For the equanimity based on subsets, 97.07 %. For the normalized version of equanimity based on subsets, 37.13 %. Among all the approaches, in the pursuit of finding a clear boundary between functions inside the dataset and the rest, the one that provides the best separation is the variable importance-based approach, followed by the non-normalized subset-based approach, al- though the separation is significantly reduced. It could be inferred that what determines a function’s equanimity is not the subsets, but rather the variables that have the same effect on the function’s output. It should be noted that this is an assumption, and an- other possibility could be that the subset-based approach requires further adjustment to accurately capture equanimity. Finally, let’s see how the corresponding graph would look like if we only consider the entanglement value. 2 4 6 8 10 12 0.0 0.1 0.2 0.3 0.4 0.5 98-percentile Dataset Non dataset Among all the metrics, this is the one that provides the best separation, as we can observe that the entanglement of all the functions in the dataset does no exceed the value of 10, which is the 98th percentile. 48 Chapter 6. Experimental results Note that even though 10 may seem like a large entanglement value, considering the maximum value is 12, the definition of entanglement selects the minimum value from a set of values. Therefore, increasing by one unit in larger values (e.g., from 10 to 11) is much challenging than increasing by one unit in smaller values (e.g., from 2 to 3). From all the results obtained by studying the metrics separately, we can conclude that they all appear to be good indicators for determining when a function is computed by a large circuit, except perhaps for the normalized version of subset-based balance. It is crucial to recognize that the presence of an intersection does not invalidate the initial conjecture. The assertion that a function is computed by a super-polynomial circuit does not imply that it necessarily possesses a significant level of both metrics. What we can indeed deduce is that by combining both metrics, we will be able to observe a clearer separation between the two sets, thus empirically confirming the main conjecture we started with. We will study the combination of both metrics in the next section. 6.1.2. Testing metrics combined A good way to assess how data is classified based on two parameters is by using heat maps: graphical representations of data where values are depicted using a color scale. The graphs we will display a significant amount of information that we need to clarify before presenting them. The x-axis represents the different values of equanimity. Since there are three ver- sions, we will provide one heat map for each version of equanimity. The y-axis represents the different values of entanglement. These values range from 2, the minimum, to 12, the maximum. At each position in the matrix, determined by the equanimity, Q, and entanglement, T , values, we calculate the percentage of functions outside the dataset that have metric values (Q(f), T (f)) greater than or equal to (Q, T ), from all the functions that have been analyzed and meet the same restriction. Formally, M [T ,Q] = |{f ∈ F \ D : (Q(f), T (f)) ⩾ (Q, T )}| |{f ∈ F : (Q(f), T (f)) ⩾ (Q, T )}| · 100 where F represents all the analyzed functions and D represents the functions in dataset. Note that the denominator can be 0, indicating there does not exist a function in F satisfying the condition. In such cases, we set it to −1. Let’s first examine the heat map when considering the equanimity metric based on variable importance. 6.1. Performance of metrics in the dataset 49 0.16 0.24 0.32 0.4 0.48 0.56 0.64 0.72 0.8 0.88 I 12 .0 11 .0 10 .0 9. 0 8. 0 7. 0 6. 0 5. 0 4. 0 3. 0 2. 0 100.00 100.00 100.00 100.00 100.00 100.00 -1.00 -1.00 -1.00 -1.00 100.00 100.00 100.00 100.00 100.00 100.00 100.00 -1.00 -1.00 -1.00 99.98 99.98 99.98 99.99 100.00 100.00 100.00 100.00 -1.00 -1.00 96.78 96.78 96.79 99.64 99.99 100.00 100.00 100.00 -1.00 -1.00 79.37 79.37 80.08 96.06 99.90 100.00 100.00 100.00 100.00 -1.00 57.72 57.72 60.19 89.93 99.76 100.00 100.00 100.00 100.00 100.00 51.71 51.84 55.56 87.14 99.56 99.99 100.00 100.00 100.00 100.00 50.13 50.29 54.35 85.99 99.44 99.99 100.00 100.00 100.00 100.00 50.01 50.20 54.29 85.92 99.40 99.97 99.97 100.00 100.00 100.00 50.00 50.19 54.29 85.92 99.40 99.97 99.97 100.00 100.00 100.00 50.00 50.19 54.29 85.92 99.40 99.97 99.97 100.00 100.00 100.00 0 20 40 60 80 100 From here, we can deduce the following: When moving from left to right within each row, we can observe an increase in the percentage. This indicates that as equanimity increases, the percentage of functions outside the dataset also increases. The same can be said when moving from bottom to top with entanglement. The most interesting conclusion from this graph is that except for the lower-left square and the -1 values in the upper-right corner, only functions outside the dataset surpass the imposed constraints on equanimity and entanglement. Note that the -1 values appearing in the top right corner could indicate that finding highly equanimous and highly entangled functions is very challenging. In the search of identifying a mathematical property that can indicate when a function is not in P/poly, as we previously mentioned, it cannot be a natural proof. As we have 50 Chapter 6. Experimental results seen, these metrics can be computed in polynomial time with respect to the input truth table, satisfying the first condition of a natural proof. The fact that finding a highly equanimous and highly entangled function is so difficult helps us bypass this definition of natural proof (in particular, its largeness condition), making it plausible to define that mathematical property based on these metrics. Now let’s examine the resulting graph when using the equanimity based on subsets. -17.1 -15.28 -13.45 -11.62 -9.79 -7.96 -6.13 -4.31 -2.48 -0.65 S 12 .0 11 .0 10 .0 9. 0 8. 0 7. 0 6. 0 5. 0 4. 0 3. 0 2. 0 100.00 100.00 100.00 100.00 100.00 100.00 100.00 100.00 100.00 -1.00 100.00 100.00 100.00 100.00 100.00 100.00 100.00 100.00 100.00 -1.00 99.98 99.98 99.98 99.98 99.99 100.00 100.00 100.00 100.00 -1.00 96.78 96.78 96.83 97.37 98.50 99.34 99.74 99.89 100.00 -1.00 79.37 79.39 80.33 83.97 89.39 94.00 96.46 98.61 99.98 -1.00 57.72 57.90 59.61 64.78 72.40 81.10 88.45 95.63 99.43 -1.00 51.72 51.96 53.79 58.97 66.89 76.16 84.32 92.78 98.11 -1.00 50.16 50.45 52.34 57.43 65.23 74.49 82.93 91.69 97.54 -1.00 50.03 50.33 52.22 57.29 65.08 74.32 82.74 91.48 96.88 2.33 50.03 50.32 52.22 57.28 65.08 74.31 82.74 91.48 96.88 2.33 50.03 50.32 52.22 57.28 65.08 74.31 82.74 91.48 96.88 2.22 0 20 40 60 80 100 Here, an increase in the size of the square in the bottom-left can be observed. However, it still functions as a good indicator, leading to the same conclusions as in the previous case. A worst scenario is presented when we use the equanimity based on subsets normalized. 6.1. Performance of metrics in the dataset 51 0.48 0.52 0.57 0.62 0.66 0.71 0.75 0.8 0.84 0.89 ´S 12 .0 11 .0 10 .0 9. 0 8. 0 7. 0 6. 0 5. 0 4. 0 3. 0 2. 0 100.00 100.00 100.00 100.00 100.00 -1.00 -1.00 -1.00 -1.00 -1.00 100.00 100.00 100.00 100.00 100.00 100.00 -1.00 -1.00 -1.00 -1.00 99.98 99.98 99.99 100.00 100.00 100.00 100.00 -1.00 -1.00 -1.00 96.78 96.89 98.61 99.62 99.81 99.78 100.00 100.00 -1.00 -1.00 79.37 80.83 89.95 95.68 97.29 92.48 93.49 100.00 100.00 -1.00 57.72 60.64 72.86 84.91 86.57 72.57 48.65 60.68 100.00 -1.00 51.74 54.73 66.96 79.40 79.54 51.19 19.28 10.27 12.15 6.25 50.18 53.24 65.25 77.77 77.49 47.56 16.85 8.99 12.38 6.25 50.05 53.10 65.09 77.56 77.07 46.35 15.30 6.45 3.39 0.28 50.05 53.10 65.08 77.55 77.06 46.34 15.28 6.45 3.39 0.28 50.05 53.10 65.08 77.55 77.06 46.34 15.28 6.45 3.38 0.28 0 20 40 60 80 100 In this graph we see an unusual phenomenon that did not happen in the previous two cases. For entanglements less than 6, it no longer holds that as equanimity increases, the percentage also increases. On the other hand, it is worth considering how the histograms for entanglement would look if we only take into account the functions that exceed the 98th percentile of equanimity. For example, for equanimity based on variable importance, we would obtain the following graph. 52 Chapter 6. Experimental results 1 2 3 4 5 6 7 8 9 10 11 12 0.0 0.2 0.4 0.6 0.8 1.0 Dataset Non dataset Here, the separation is clear, and both sets are perfectly distinguishable. However, the graphs for equanimity based on subsets do not separate entirely both datasets and there is still some intersection, although is considerably smaller. 1 2 3 4 5 6 7 8 9 10 11 12 0.0 0.1 0.2 0.3 0.4 0.5 Dataset Non dataset 6.2. Scalability of metrics 53 1 2 3 4 5 6 7 8 9 10 11 12 0.0 0.1 0.2 0.3 0.4 0.5 Dataset Non dataset In conclusion, the results demonstrate that it would be possible to find a threshold using both metrics in order to classify whether a function is computed by a small or large circuit. It is worth noting that, based on the data obtained, the best definition of equanimity appears to be the one based on variable importance. In order to define a potential mathematical property of functions outside of P/poly based on these metrics, large bounds should be chosen for these values to avoid it being satisfied by a large proportion of functions. As observed, it is challenging to find a function that is highly equanimous and entangled. 6.2. Scalability of metrics This experiment shows how our metrics perform as the input bits size increases. In order to so, we have calculated our metrics on 100,000 functions of n bits to 1, for n ∈ {4, ..., 10}. Besides, we obtained the value of our metrics on the decision problems introduced in Section 3.23. Note that 100,000 represents a really small percentage of 2n for n ⩾ 5, but calculating our metrics becomes increasingly challenging as n increases. This is due to the fact that many of our metrics have quadratic complexity in relation to the size of the truth table (which in turn is exponential with the number of input variables), as we have shown in previous chapters. Anyway, it will be a good indicator to understand the behavior of the decision problems. 3Let us recall the notation introduced in previous chapters: pn for PARITY; mn for MAJORITY; Pn for PRIMALITY; Cn for CLIQUE; C ′ n for CLIQUE′ 54 Chapter 6. Experimental results Before showing the results, we will define a new problem. As we explained in Section 5.5, the PRIMALITY problem (Pn) could be an example of a high-entangled, low-equanimous problem. With a similar reasoning we used to define CLIQUE′ (i.e., that combining a problem with PARITY makes it more equanimous) we can define the following problem: Definition 6.2.1 (PRIMALITY′). Given a binary input, it returns 1 if: The number of ones is even and the corresponding number is prime The number of ones is odd and the corresponding number is not prime It can be represented as the family of functions {P ′ n : n ∈ N} P ′ n : Zn 2 −→ Z2 x 7→ P ′ n(x) = pn(x)⊕ Pn(x) Note this problem belongs to P/poly (since it belongs to P), so if it was highly equanimous, since it seems to be entangled, it would go against our conjecture. In the following figure, we will show how the chosen decision problems perform against the random sample of functions (with the equanimity based on the survival of subsets). To achieve this, we will compute the 98th percentile for each metric within that sample of functions and examine whether the values of the selected decision problems fall below or above this threshold. In particular, we consider n = 6 and n = 10, since for other values of n a complete graph cannot be formed (for a graph of v vertices, a complete graph needs v(v−1) 2 edges). p6 M6 P6 P ′6 C6 C ′6 40 30 20 10 0 S Values for n = 6 6.2. Scalability of metrics 55 p10 M10 P10 P ′10 C10 C ′10 7000 6000 5000 4000 3000 2000 1000 0 S Values for n = 10 As we can observe, the equanimity value of CLIQUE′ is always above the threshold. In fact, in both cases its value is greater than the maximum value obtained from the random sample. This observation suggests CLIQUE′ is indeed a really equanimous problem. It is evident that the unbiased nature of the PARITY problem has also influenced the PRIMALITY problem. However, although PRIMALITY′ gains equanimity, it is still not enough to surpass the threshold. Somehow, this unbiasing effect PARITY has is more effective on the CLIQUE problem, and this could be related to the inherent nature of the problem. Since CLIQUE is invariant under isomorphism, it becomes easier to enhance its equanimity since it already possesses the property of being unbiased in that regard. In the following graph, we display the results for the equanimity based on the importance. 56 Chapter 6. Experimental results p6 M6 P6 P ′6 C6 C ′6 0.0 0.2 0.4 0.6 0.8 1.0 I Values for n = 6 p10 M10 P10 P ′10 C10 C ′10 0.0 0.2 0.4 0.6 0.8 1.0 I Values for n = 10 The conclusions that can be extracted are similar. However, although its value is inferior to the CLIQUE′, in this case PRIMALITY′ does surpass the threshold. As we can observe, the value at the 98th percentile is not significantly high. This suggests that while this definition of equanimity may be useful for determining whether a function is equanimous or not in general terms, it might not be as effective in identifying extreme cases (which is our goal). 6.2. Scalability of metrics 57 Let’s see what happens with the entanglement metric: p6 M6 P6 P ′6 C6 C ′6 0 2 4 6 8 10 12 14 16 Values for n = 6 p10 M10 P10 P ′10 C10 C ′10 0 10 20 30 40 50 60 Values for n = 10 As it becomes evident, even though CLIQUE′ has a high level of entanglement, it does not surpass the threshold. Following our intuitions from previous chapters, keeping equa- nimity while becoming more entangled is gate-consuming. This is why it is not necessary that the problem we are looking for is totally equanimous and totally tangled, since we suspect that, for highly equanimous problems, there exists a certain value of entanglement 58 Chapter 6. Experimental results beyond which the circuit that computes the function cannot be polynomial in size (and this value does not have to be the maximum). In the following graphics, we will observe the evolution of out metrics’ values as n gets bigger starting with QS. 4 5 6 7 8 9 10 7000 6000 5000 4000 3000 2000 1000 0 S pn Mn Pn P ′n Cn C ′ n 98th Percentile Despite the fact that the range of possible values of QS notably expands within n, the value of the 98th percentile remains relatively consistent. As we explained with the pre- vious diagrams, CLIQUE′ always surpasses that threshold, while PRIMALITY′ seems to distance from it. The other decision problems also act as expected by distancing from the boundary. This indicates their lack of equanimity gets more noticeable as n increases. Let’s show now the graphic for the entanglement. 6.3. Mitigating bias in Boolean circuits 59 4 5 6 7 8 9 10 10 20 30 40 50 60 pn Mn Pn P ′n Cn C ′ n 98th Percentile As we mentioned earlier, every decision problem falls below the value of the 98th percentile. However, it is noticeable that the growth tendency of PARITY and MAJORITY is very different from the one CLIQUE and PRIMALITY have. We expect the growth of CLIQUE becomes more notorious as n increases than the growth of PRIMALITY. This is because the CLIQUE problem becomes more complex while the PRIMALITY problem becomes simpler as n increases (as a result, the information shared between the partitions will become more concise relative to n). 6.3. Mitigating bias in Boolean circuits In this section we will study how Boolean circuits that are biased towards a certain subset of the input in the first level may (or may not) be capable of mitigating this bias and becoming more equanimous. We will test this behavior in Boolean circuits expressed in Alternating Circuit (AC) Form, defined in 3.2.2. It is reasonable to think that a circuit in which a pair of inputs are connected with an AND gate in the first level is more likely to bias towards that pair in the function computed by that circuit rather than a circuit without that gate. Based on this, we will create random circuits that satisfy: i) x1 AND x2 is ALWAYS in level 1; ii) x3 AND x4 is NEVER in level 1. This should imply, based on our assumptions about equanimity, that functions computed by these circuits are almost always more biased towards {x1, x2} than {x3, x4} regarding the columns of its truth table where the output is 1. There are two extreme cases we take into consideration. In the first one, the output of x1 AND x2 is preserved in one branch until the last level, i.e., there exists only one gate 60 Chapter 6. Experimental results in level 2 whose input is the output of x1 AND x2, and the output of this level-2-gate is the input of only one gate in level 3 (and so on). On the contrary, in the second one, we poison the second level with x1 AND x2, i.e., every gate of level two has the output of x1 AND x2 as one of its inputs. Let’s show an example of each case to visualize them, starting with the first case (the output is preserved in a branch). x1 x2 x̄2 x4 x1 x3 x4 x5 As evident from the diagram, the gates influenced by the output of the gate x1 AND x2, which are highlighted in red, are kept on a specific part of the circuit. Let’s now see the other case, in which we poison every gate of the first level. x1 x2 x̄2 x4 x1 x3 x4 x5 6.3. Mitigating bias in Boolean circuits 61 As we can observe, by injecting the output of x1 AND x2 in every gate of the second level, it continues to propagate and influence every gate through the following levels. With the aim of testing if our intuitions are accurate, we have generated two samples of functions computed by circuits that satisfy our restrictions (one sample for those in which we keep x1 AND x2 in a branch and another for those in which we poison the first level) and consist of a maximum of 50 gates. The results of our analyses are outlined below. 6.3.1. Keeping x1 AND x2 in a branch As we have introduced, these circuits keep x1 AND x2 in a certain branch and the rest of the circuit is formed (almost) randomly — keep in mind x3 and x4 are never connected in the first level.— This was achieved by selecting a random number of gates for each level. One of the inputs of the first gate is connected to the output of the branch that computes x1 AND x2, and the other input is selected randomly among the outputs of the inferior level. The inputs of the rest of the gates are also selected randomly, but in this cases the output of the branch that computes x1 AND x2 is not considered. Intuitively, the bias towards {x1, x2} could be evened out in two ways: The part of the circuit that does not contain this branch should somehow connect x3 and x4 during the upper levels, thereby augmenting the influence of {x3, x4}. Introducing ¬x1 or ¬x2 into the branch, thereby diminishing the influence of {x1, x2}. Let’s show which percentage of the sample manages to mitigate the bias by comparing the proportion of circuits whose computed function returns 1 for input cases where each pair is respected more than the other pair. 60% 15% 25% x1 AND x2 > x3 AND x4 x1 AND x2 == x3 AND x4 x1 AND x2 < x3 AND x4 62 Chapter 6. Experimental results As we expected, the bias towards {x1, x2} is preserved in more than half of the cases. However, it is remarkable that 1 out of 4 circuits successfully shift the balance towards x3, x4, despite our efforts to prevent their connection at the first level. Therefore, there is an important factor to consider: depth. Obviously, as a circuit grows deeper, it becomes more likely that it satisfies the require- ments to even out the bias we pointed out before. If we were to solely consider the first level, the circuit would exhibit an inherent bias towards x1, x2 rather than x3, x4 (as one gate is consistently added while the other is not). Hence, it becomes imperative to incor- porate additional levels to enhance the interconnections between outputs and achieve a more equanimous circuit. In the graph below, we show how depth affects the percentage of times {x1, x2} is more present in the output than {x3, x4}, i.e., the bias is not mitigated. 0 1 2 3 4 5 6 7 8 9 10 11 Depth 0 10 20 30 40 50 60 70 80 90 100 Pe rc en ta ge The bias decreases as the circuits grows deeper, as anticipated. In fact, there comes a point (around depth = 9) where x1, x2 ceases to be predominant in half of the instances. 6.3.2. Poisoning the first level with x1 AND x2 In this section, we will analyze the sample that contains the circuits in which every gate of the second level has x1 AND x2 as one of its inputs and never includes x3 AND x4. Contrary to the previous case, reducing the influence of {x1, x2} in this type of circuits is way more complicated, since it appears in almost every branch. We can draw a parallel between this situation and an infectious disease. If we isolate some cases and treat them locally, it would be viable to stop it from spreading. However, once it has already spread extensively, reducing its impact becomes exceedingly challenging. 6.3. Mitigating bias in Boolean circuits 63 In the following graph we display the percentage of circuits of the sample that are able to mitigate the bias: 98% 2% x1 AND x2 > x3 AND x4 x1 AND x2 == x3 AND x4 As we anticipated, it is almost impossible to mitigate the bias towards {x1, x2} in this type of circuits. Furthermore, the balance is never shifted towards {x3, x4}. In contrast to the previous scenario, not even growing deeper will solve the problem because more and more branches will be created and x1 AND x2 will have an influence in most of them. We appreciate this in the following chart: 2 3 4 5 6 7 8 9 10 11 Depth 0 10 20 30 40 50 60 70 80 90 100 Pe rc en ta ge 64 Chapter 6. Experimental results 6.3.3. Conclusions In circuits in AC form, connecting two variables in the first level amplifies their impact on the output (while the opposite occurs if they are not connected). Based on the experiment conducted above, mitigating the bias towards those inputs is possible when keeping them in a branch since the bias diminishes along depth, and it is almost impossible if we do exactly the opposite. The first approach is similar to the one utilized by the PARITY function. The standard XOR-based circuit that computes this function keeps each output of the first level on a single branch (and the equivalent circuit in AC form bounds the reach of each output of the first level to only two gates of each level of the circuit). This is how it manages to give each pair of inputs the same importance, being totally equanimous but very low entangled. As demonstrated, in order to achieve bias mitigation, circuits must possess a certain depth. This gives an intuition on why the PARITY function does not belong to the AC0 class, which consists of polynomial-sized, constant-depth circuits. The second approach shows that when a circuit is entangled by a specific pair, it is almost impossible to mitigate its bias. Intuitively, the only feasible method to counteract this effect would be to employ a similar strategy with the remaining possible pairs. This could be achieved by injecting every output of the first level into various branches, and since gates have fan-in 2, this would result in an increase on the number of gates. Something similar would happen in the levels above. In conclusion, an entangled circuit needs to keep growing in order to assure equanimity. This is why our conjecture suggests that, for an entangled function to achieve equanimity, it would require a large (ideally superpolynomial) number of gates. Chapter 7 Conclusions and future work The study conducted on Boolean functions in this text aims to make a useful contribution to Computational Complexity. The results obtained so far show that, although ambitious, it seems plausible to provide a deeper analysis on what makes a function computable with either small or big circuits based on our metrics. Since the conception of circuit complexity, there have been scarce advancements in this field. Therefore, any progress is interesting by itself. Throughout this text, we have explained and measured certain properties (equanimity and entanglement) that have the potential to make circuits superpolynomial in size. These properties are significant in the context of establishing lower bounds for circuits, as they provide insights into the inherent complexity of computational problems. As we have explained, establishing these lower bounds is a key aspect of tackling the P vs NP problem. The initial conjecture, which stated that a problem with high values of entanglement and equanimity must be computed by a circuit with high number of gates, was supported by the experimental results displayed on Chapter 6. As it seems to be promising, we propose several paths for further development of this approach. Firstly, the metrics could be refined and perfected. One could think that, since there ap- pears to be a correlation between entanglement and number of required gates, a promising way to find lower bounds would be to show inductively that circuits with a certain value of entanglement cannot be computed by polynomial-sized circuits, and then showing an NP-Complete problem (CLIQUE′ for example) which has at least that value of entangle- ment. However, as we anticipated in the first chapters, a strategy along these lines is not likely to succeed since it would be considered a natural proof. This is why we think that, even though our metrics seem to work fine for small values of n, they must be defined in a more complex way in order to capture more accurately the desired behaviors. For example, the entanglement could be calculated recursively, i.e., for each partition, obtain the local entanglement of each subset, and so on. This would highlight the fact that a very tangled function is tangled at every level. 65 66 Chapter 7. Conclusions and future work Secondly, we could study the equanimity more in depth by analyzing potential biases that can arise at different gate counts in circuits. To achieve this, we can proceed as follows. For k ∈ N, take every Boolean function that can be computed by a circuit of at most k gates. For each function, for every subset of input variables of a certain size obtain all the possible values cxS and add them into a list. Then sort each list in either ascending or descending order and add them into a set, denoted Ak. Note that, since functions computed by circuits of the same size are expected to exhibit similar bias structures, the number of elements of Ak should not be large. The ultimate goal would be to identify a certain invariant that evidences how the bias pattern becomes more complex as k grows. Following the line of the first proposal and as a possible critique to the conjecture pro- posed, one might wonder if the equalizing effect that PARITY has on CLIQUE could be transferred to another simple and entangled problem; as we saw in Section 5.5, PRIMAL- ITY fits this description. In fact, this is what happens, as we saw in Section 6.2. This potentially contradicts the conjecture we put forward. However, as we observed in the experiment, the equalizing effect provided by PARITY in PRIMALITY is not as effective as the one provided in CLIQUE. What we can conclude is that the trick would lie in de- termining sufficiently high bounds that avoid both the definition of natural proof and the identification of PRIMALITY as a super-polynomial function, while keeping CLIQUE’ within those bounds. Furthermore, perhaps PRIMALITY is not as entangled as we as- sumed. During the process of studying the defined metrics, we have realized that, in order to obtain a promising approach to tackle the P vs NP problem based on the proposed ideas, it would be necessary to utilize various branches of discrete mathematics. Perhaps the most prominent branch would be combinatorics, due to the nature of the definitions and the proofs presented in the text. Counting techniques are needed to estimate the growth of circuits that compute Boolean functions as the complexity increases. Besides, knowledge of set theory would also be necessary, as it relates to counting combinatorics. Determining applications that exhibit injectivity or even bijectivity would be crucial in establishing relationships between the cardinalities of both sets. Finally, with the last experiment proposed as future work — the one involving the Ak’s — we believe it could be interesting to apply Number Theory to determine a possible pattern that these vectors satisfy in order to provide further insights into how these Boolean functions behave with respect to the metric of equanimity. Personal contributions Following this, each of the authors will outline their personal contributions to the project. However, we would like to emphasize that the vast majority of the work has been developed collaboratively, and there is no part of the project that has been exclusively developed by any one of us. Enrique Carro Garrido The project began with a research phase, aimed at familiarizing ourselves with the con- cepts of circuit complexity that have been frequently mentioned throughout the exposition of the work, as well as the new concepts explained to us by our tutors. These new con- cepts — equanimity and entanglement — were gradually modeled throughout the work to fit our intended capture. In particular, I realized that it was not feasible to consider all possible partitions for entanglement since it would significantly reduce the range of the metric, as mentioned in Section 5.2. During this phase, our working philosophy consisted of distributing the readings among ourselves in order to achieve a broader spectrum of knowledge, and then gathering them to share the acquired insights. I specifically had to study Celia’s work [RM22] in order to understand the demonstrative techniques she presented at the end of her projects as future work. I was the creator of the Git repository [CC23]. In this repository we implemented the code for the metrics described in Sections 4.2.1 and 4.3.2. There can also be found the experi- ments described in Chapter 6. There has not been any part of the code that we did not work on together, but eventually each of us has contributed more significantly to certain parts of that repository. In particular, I took more responsibility in the implementation of the entanglement metric and the benchmarks. Regarding the experiments developed in the project, it is impossible to indicate who con- tributed more significantly as we gathered in study rooms to conduct them. The work 67 68 in these study rooms consisted in sharing ideas using the room’s whiteboard, considering them valid or providing critiques. We greatly appreciated the opportunity to work to- gether as it allowed us to develop a greater number of ideas than would have been possible working individually. There has been a greater division of tasks in the writing of the report, although everything that has been written by one of us was meticulously reviewed by the other to avoid typos and improve the writing as much as possible, many of them have been significantly modified by José. Therefore, it should be understood that I wrote the core content of the section and not that I completed the entire part. Similarly, I have made a smaller contribution to the sections he has written. In Chapter 2, I was solely responsible for writing Section 2.2 in the different proof tech- niques that have been used in the past to attempt to solve the problem P vs NP. On the other hand, I did contribute more in Chapter 3, particularly in Section 3.1, where I give a brief prior explanation of both concepts, and Section 3.3 on the descriptions of the different experiments that have been carried out. However, I had less influence on Section 3.2 where I only provided Theorem 3.2.1, showing that CLIQUE’ is NP-Complete. Later on, in Chapters 4 and 5, the collaborative work between both of us is further intensified. The complexity of the definitions and the desire to fully capture both abstract concepts have perhaps been the slowest and most progressive process of all the project. The formalization of the concept came after trial and error with experiments until they aligned with our intended objectives. Subsequently, we were able to develop the theoretical results presented in the final sections, which validate our initial intuitions. Therefore, what we did was formalize everything before writing it in the report and then distribute the results among ourselves to write them in the text. In Chapter 4, I took care of providing introduction to the concept, Section 4.1 and I also wrote the alternative to the subset-based definition of equanimity in Section 4.3.1 and Theorem 4.4.1 on the limits of equanimity. On the other hand, in Chapter 5, I took charge of writing Section 5.1, which introduces the concept of entanglement, and its formal definition in Section 5.2, except for Theorem 5.2.2 that José handled. Regarding Section 5.3 on properties of entanglement, I wrote Property 5.3.2. I also wrote Section 5.5 discussing the need to continue considering equanimity. The distribution of work in Chapter 6 has been more separate. In particular, I took charge of Section 6.1, which describes and presents the results of the first experiment on testing the metrics using José’s dataset. It is also worth mentioning that once we completed all the experiments, it occurred to me that we may not have considered the equanimizing effect that PARITY had with CLIQUE could also be applied to PRIMALITY. Therefore, we had to add this benchmark as well, realizing that it did indeed exhibit a significant level of equanimity, although not as much as CLIQUE’ does. 69 Finally, the chapter on conclusions and future work was written collaboratively, although if we had to assign specific parts to each of us, I would take responsibility for the future work section, while my partner would be in charge of the conclusions part. Setting aside the report, I have been the one with the most communication with the tutors through email. However, it is important to note that all messages were agreed upon beforehand between the two team members. I want to emphasize that the work has been done together, there has not been any person who has done more work that the other, and anything that I have stated as my own contribution has been highly influenced by my colleague José. José Ramón Cobián Fernández At the beginning of the project, I read in detail the sixth chapter of the book Computa- tional Complexity: A Modern Approach [AB09] which explains how Boolean circuits are related to the P ̸= NP problem and why this relationship is important. At the same time, I was reviewing the bachelor’s theses by Celia Rubio [RM22] and Jorge Villarru- bia [VE21], since they were about the same topic and their conclusions could serve as a starting point for our work. Then, after some meetings with our tutors, we started to formalize and experiment with the concepts of equanimity and entanglement. This process involved extensive brainstorm- ing and in-depth discussions of ideas. This particular aspect of the project was highly collaborative, given that the concepts in question were abstract in nature and constituted a critical component of our work. Hence, it was imperative to ensure their definition was as accurate as possible. In order to test them experimentally, we had to implement the code for calculating the metrics associated with the defined concepts. I programmed the files that solved the deci- sion problems MAJORITY and PRIMALITY, introduced in Section 3.2. I also developed the code that implemented each definition of the equanimity metric. This required revis- iting and adjusting the code, since each approach was perfected over time. Additionally, there were some approaches we created and then discarded as they did not reflect the expected behaviors. Regarding the writing of the report, I took responsibility for Chapter 1, which serves as an introduction to the topic. In this chapter, we present our objectives, outline our work plan and provide an overview of how the project is structured, including the contents of each chapter. Furthermore, I wrote sections 2.1 and 2.3, in which we introduce essential definitions necessary to understand the P vs NP problem and circuit complexity, as well as explaining how they are connected. This required extensive research to find the most 70 relevant and up-to-date references and information related to the topic. Following that, I composed a significant portion of Section 3.2, where we introduced the chosen decision problems and their relevance. This included developing most part of the definitions and the proof of Lemma 3.2.1, which states the Half CLIQUE problem is NP-Complete. In chapters 4 and 5, which are the theoretical core of the project, we collaborated in formulating the definitions and results. In particular, I conceived the idea that it could be interesting to consider the importance of variables in order to define equanimity. This was the starting point of the creation of the equanimity based on the importance of each variable introduced in Section 4.2. Furthermore, I observed that the entanglement values of PARITY and MAJORITY followed a certain pattern as n increased, which led to the inclusion of Theorems 5.2.1 and 5.2.2. Regarding the proofs, we came up together with the main ideas and then distributed the work to formalize them. I took charge of those concerning Proposition 4.3.1, Theorems 4.4.2 and 5.2.2, and Lemmas 5.3.1 and 5.2.1. Moreover, I had a major influence on the developments of sections 4.2.1, 4.3.2 and 5.4 regarding the implementation of the metrics. We divided the inclusion of the definitions into the report, and I took responsibility for those related to equanimity, which are doc- umented in Sections 4.2 and 4.3 (except for the alternative to the definition covered in Section 4.3.1, which was written by Enrique). Besides, I selected and included suitable examples to enhance the comprehension of these definitions. With respect to the experiments, we selected which experiments to conduct and analyzed their results together, whereas we divided the implementation of the required code. I wrote the code used to obtain the samples used in the experiment Scalability of metrics explained in Section 6.2 and the one that generated the circuits used in Section 6.3.2. Then, I created the Python code needed to obtain the graphs displayed in Section 6.2 and in Section 6.3. Lastly, I wrote the concepts of those two sections, which reflect the results and conclusions derived from our collaborative analysis. Finally, we agreed on which were the most significant conclusions we derived and de- termined the approach for future work. In the corresponding chapter, Chapter 7, I was responsible for the paragraphs that focus on the conclusions, while Enrique explained how the work could be further advanced. It is also worth mentioning that when our tutors provided feedback on specific sections of the project, I was in charge of revisiting those parts and refining them based on their comments and suggestions. Putting the report aside, my responsibility involved thoroughly reviewing and providing comments on the code contained within the repository. This included testing every func- tionality to ensure every piece of code was performing as expected and the data that was being generated and used in our experiments was correct. Furthermore, I made adjust- ments to align the names of functions and variables with those utilized in the report. Additionally, I added comments preceding each function to explain their purpose and functionality. 71 In conclusion, I want to highlight the high level of collaboration that defined our work. Throughout the project, every aspect that required the creation of new definitions and results was a collaborative effort aimed at ensuring their quality and accuracy. This is why, although we divided the technical and writing aspects of the report between us, this work is the result of mutual effort. Bibliography [AB09] S. Arora, B. Barak: Boolean circuits. En Computational Complexity: A Modern Approach, pp. 106–122. Cambridge University Press, 2009. https://doi.org/10. 1017/CBO9780511804090.009 [AS16] S. Aaronson: P ? = NP. Open problems in mathematics, Springer, 2016, pp. 1–122. https://link.springer.com/chapter/10.1007/978-3-319-32162-2_1 [BGS75] T. Baker, J. Gill, R. Solovay: Relativizations of the P=?NP Question, SIAM Journal on Computing, 4(4):431–442, 1975. https://doi.org/10.1137/0204037 [CF23] J. R. Cobián Fernández: Generación de circuitos para experimentos de comple- jidad. Trabajo de Fin de Grado en Matemáticas, Departamento de Sistemas Infor- máticos y Computación, Universidad Complutense de Madrid, 2023. [CC23] E. Carro Garrido, J. R. Cobián Fernández: Repositorio del presente trabajo, 2023. https://github.com/encarro12/TFG-Circuit-Complexity.git [Had96] J. Hadamard: Sur la distribution des zéros de la fonction ζ(s) et ses conséquences arithmétiques. Bulletin de la Société mathématique de France, vol. 24, pp. 199–220, 1896. http://www.numdam.org/item/10.24033/bsmf.545.pdf [Hå14] J. Håstad: On the correlation of parity and small-depth circuits, SIAM Journal on Computing, vol. 43, no. 5, pp. 1699–1708, 2014. Publisher: SIAM. https://epubs. siam.org/doi/abs/10.1137/120897432 [Ho09] R. Horodecki, P. Horodecki, M. Horodecki, and K. Horodecki, Quantum en- tanglement, Reviews of Modern Physics, vol. 81, no. 2, pp. 865, 2009. https: //journals.aps.org/rmp/abstract/10.1103/RevModPhys.81.865 [Po35] T. Popoviciu: Sur les équations algébriques ayant toutes leurs racines réelles, Mathematica, vol. 9, no. 129-145, p. 20, 1935. [RM22] C. Rubio Madrigal: Búsqueda de funciones booleanas complejas: construcciones mediante monotonía y relación entre repetitividad y endogamia, 2022. 72 https://doi.org/10.1017/CBO9780511804090.009 https://doi.org/10.1017/CBO9780511804090.009 https://link.springer.com/chapter/10.1007/978-3-319-32162-2_1 https://doi.org/10.1137/0204037 https://github.com/encarro12/TFG-Circuit-Complexity.git http://www.numdam.org/item/10.24033/bsmf.545.pdf https://epubs.siam.org/doi/abs/10.1137/120897432 https://epubs.siam.org/doi/abs/10.1137/120897432 https://journals.aps.org/rmp/abstract/10.1103/RevModPhys.81.865 https://journals.aps.org/rmp/abstract/10.1103/RevModPhys.81.865 BIBLIOGRAPHY 73 [RR94] A. A. Razborov, S. Rudich: Natural proofs, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pp. 204–213, 1994. https://dl.acm.org/ doi/pdf/10.1145/195058.195134 [RW93] A. Razborov, A. Wigderson: nΩ (log n) lower bounds on the size of depth-3 threshold cicuits with AND gates at the bottom, Information Processing Letters, vol. 45, no. 6, pp. 303–307, 1993. Publisher: Elsevier. https://www.sciencedirect. com/science/article/pii/0020019093900417 [Sha49] C. E. Shannon: The synthesis of two-terminal switching circuits, The Bell System Technical Journal, vol. 28, no. 1, pp. 59–98, 1949. Publisher: Nokia Bell Labs. https: //ieeexplore.ieee.org/abstract/document/6771698/ [Tur36] A. M. Turing: On Computable Numbers, with an Application to the Entschei- dungsproblem. Proceedings of the London Mathematical Society, s2-42(1):230–265, 1936. https://doi.org/10.1112/plms/s2-42.1.230 [VP96] C. de la Valle-Poussin, Recherches analytiques sur la théorie des nom- bres premiers, Ann. Soc. Sc. Bruxelles, 1896. https://cir.nii.ac.jp/crid/ 1573950400259760768 [VE21] J. Villarrubia Elvira: Identificación experimental de las funciones booleanas que requieren circuitos extensos y aplicación al estudio de P vs NP, 2021. [Wig06] A. Wigderson: P, NP and mathematics–a computational complexity perspective. Proceedings of the ICM, vol. 6, pp. 665–712, https://www.math.ias.edu/~avi/ PUBLICATIONS/MYPAPERS/W06/w06.pdf https://dl.acm.org/doi/pdf/10.1145/195058.195134 https://dl.acm.org/doi/pdf/10.1145/195058.195134 https://www.sciencedirect.com/science/article/pii/0020019093900417 https://www.sciencedirect.com/science/article/pii/0020019093900417 https://ieeexplore.ieee.org/abstract/document/6771698/ https://ieeexplore.ieee.org/abstract/document/6771698/ https://doi.org/10.1112/plms/s2-42.1.230 https://cir.nii.ac.jp/crid/1573950400259760768 https://cir.nii.ac.jp/crid/1573950400259760768 https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W06/w06.pdf https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W06/w06.pdf Página de Título Abstract Índices Tabla de Contenidos Introduction State of the art P vs NP Problem Techniques to solve P vs NP Circuit complexity Presentation of the new approach Equanimity and entanglement Decision problems of interest Problems known to be in P/poly CLIQUE Decision Problems Experiments to support the conjecture Equanimity Introduction to the concept of equanimity Equanimity based on the importance of each variable Implementation for QI Equanimity based on the survival of subsets Alternative to the definition Implementation for QS Limits of equanimity Entanglement Introduction to the concept of entanglement Entanglement formal definition Properties of entanglement metric Implementation for T Do we still need equanimity? Experimental results Performance of metrics in the dataset Testing the metrics individually Testing metrics combined Scalability of metrics Mitigating bias in Boolean circuits Keeping x1 AND x2 in a branch Poisoning the first level with x1 AND x2 Conclusions Conclusions and future work Personal contributions Bibliography