Analysis of Boolean functions using equanimity and entanglement

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 significant efforts, fundamental questions regarding the complexity and behavior of Boolean functions remain unresolved. The lack of comprehensive mathematical models and techniques 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 fundamentales 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 superpolinó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. PvsNPProblem................................ 4 2.2. Techniques to solve P vs NP . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3. Circuitcomplexity ............................... 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. Limitsofequanimity .............................. 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. Scalabilityofmetrics.............................. 53 6.3. Mitigating bias in Boolean circuits . . . . . . . . . . . . . . . . . . . . . . 59 6.3.1. Keeping x1AND x2inabranch.................... 61 6.3.2. Poisoning the first level with x1AND 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 con1Our notion of entanglement will be somehow inspired by quantum entanglement from physics, although we are not aware of any applications of related ideas to the classification of Boolean functions. 1 2Chapter 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 formalization. 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 6presents 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 discussion 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 expressed 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 introduced Turing machines. 4 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. Anatural 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 fn1(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 condition. 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−1monomials of length nand all conjunctive normal forms have the maximal number of 2n−1clauses 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→ yis prime, where y=Pn 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, xi= 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 contributes 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 isomorphismequivalent, 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 Vis the set of vertices and Eis the set of edges between those vertices, and let k∈N. A k-CLIQUE is a subgraph S= (V′, E′)with |V′|=ksuch that Sis 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 Gcontains 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∪Iand E′=E, where Iis 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 kif and only if G′has a clique of size k. k < |V| 2. Let’s take V′=V∪Mand E′=E∪F, where Mis 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 kif and only if G′has a clique of size k′. Since the Half CLIQUE problem is computationally easier, we will use it for our experiments. 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 equanimous 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| 2and |E|is even. ii. G doesn’t contain a CLIQUE of size |V| 2and |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 nand 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 Sonly 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:= Sis a complete subgraph with |V′|=|V| 2⇐⇒ ∀(u, v)∈V′,(u, v)∈E′∧|V′|= |V| 2⇐⇒ (u, v)∈V′, G[u][v]=1(if Gis 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 Pas before, let Hbe the true/false answer of the Half CLIQUE Problem for G= (V, E), it can be shown with first-order logic that PNXOR 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∧x2always appears at the first level, while x3∧x4never appears, and all circuits have a size limit of 50 gates. In the first part, we observe what happens when we enforce that x1∧x2only 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 x1in an unbiased circuit should have an effect on every other variable equally. However, if the input x1affects 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 x1is “accompanied” 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). x1x2 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 x1AND x2intersect, this forces x1to always be accompanied by x2. On the other hand, the OR gate just above has a different behavior, as it forces x1to never be accompanied by x3or x4(the set of clauses in this case is {x1∧x2, x3∧x4}). The other percentages below x5, x6, x7, x8are 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 x1and (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.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 2ntimes, 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 3PARITY 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=Pn 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 2due 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 z1, z2∈Zn−1 2such that (x1, y1) = Γ(z1) = Γ(z2) = ( x2, y2). Then, z1=x1J=x2J=z1 where xJ= (x1, ..., xi−1, xi+1, ..., xn). Surjective: Let (x, y)∈ Y, if we take z =xJ, then by definition, Γ(z)=(x, y). Well-defined: Let z1, z2∈Zn−1 2such that (x1, y1) = Γ(z1)= Γ(z2)=(x2, y2), then x1=x2=⇒z1=x1J=x2J=z1 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 X k=1 σk= 0 −σn=−1 4 Therefore, the statement is divided into two parts: σk= 0,∀1⩽k⩽n−1. Let xS∈Zk 2, with S∈ {1, ..., n}, then cxS=|{gxS(z) = 1 : z∈Zn−k 2}| =|{p⌊n 2⌋(xS)⊕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, cx =|{pn(x)=1}| ⩽1 Therefore, µn=1 ωnX xS∈Zn 2 S={1,...,n} cx =1 ωnX x∈Zn 2 cx =1 ωnX x∈Zn 2 pn(x)=1 1 = 1 ωn ·ωn 2=1 2 Then, the variance results in σn=1 ωnX x∈Zn 2 (cx −µn)2=1 ωnX 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 mechanics 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. p0p1p2 p3p4p5p6p7p8 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 klevels, 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, xS1, needs to communicate k1bits of information and the partition in the right, xS2, needs to send k2bits to compute the value of the function in x,f(x). A function is entangled if k1and k2are 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. k1bits k2bits xS1xS2 f(x) = g(xS1, xS2) 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≡1and fn≡0because the partition does not need to communicate any kind of information. This is represented in the following figure. 1For ninputs, 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 0bits 0bits xS1xS2 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, pndenotes the PARITY function for inputs consisting of nbits. p|S1|(xS1)(1bit) p|S2|(xS2)(1bit) xS1xS2 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 xin half, obtaining x1= (1,0,1) and x2= (1,1,0). The information needed from each xiis just the number of ones, so only log mbits are required, being mthe 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 Sbeing the partition of variables. When the total number of ones is gathered, ones(x), the value of the function is 1if and only if ones(x)⩾n 2. 5.1. Introduction to the concept of entanglement 33 ones(xS1)∈O(log |S1|)bits ones(xS2)∈O(log |S2|)bits xS1xS2 ones(xS1) + ones(xS2)⩾n 2 In the examples above, the number of bits required to transmit the information is independent of the partition chosen. However, in same cases a function may seem entangled when observed through certain partitions and low-entangled when observed through others. 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−→ Z2such 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 fnwould 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 2as x=w1w2, with wi∈Z n 2 2and wi=w1 iw2 i, where wj i∈Z n 4 2. Let’s take the subset S1such that w1 1and w1 2belong to it, and S2its complementary. Since w1=w2⇐⇒ wi 1=wi 2 for i∈ {1,2},S1only needs to transmit one bit to S2which indicates whether w1 1=w1 2 or not (and the same happens from S2to 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 \ Sas Sunless 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−→ Z2be a Boolean function and {S, S}be a partition of variables, where |S|=k. The information that the partition Sgives to its complementary is i(S) = |{gxS:xS∈Zk 2}| where gxS:Zn−k 2−→ Z2 gxS(xS) = 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 fas 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 Ssince 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 gfunctions. Also, since gfunctions depend on |S|bits, there can be no more than 22|S|of them. A problem arises when Sis 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 fas 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:gxS(z0) = gyS(z0)⇒ ∀z∈Z⌈n 2⌉ 2, gxS(z) = gyS(z) ii ∃z0∈Z⌈n 2⌉ 2:gxS(z0) = ¬gyS(z0)⇒ ∀z∈Z⌈n 2⌉ 2, gxS(z) = ¬gy S(z) We will prove the first statement (the second one is analogous). We can express gxSas gxS(z) = pn(x) = x1⊕x2⊕... ⊕xn=p⌊n 2⌋(xS)⊕p⌈n 2⌉(z) and since gxS(z0) = gyS(z0), we have p⌊n 2⌋(xS)⊕p⌈n 2⌉(z0) = p⌊n 2⌋(yS)⊕p⌈n 2⌉(z0) so 2 p⌊n 2⌋(xS) = p⌊n 2⌋(yS) We can conclude, ∀z∈Z⌈n 2⌉ 2, gxS(z) = p⌊n 2⌋(xS)⊕p⌈n 2⌉(z) = p⌊n 2⌋(yS)⊕p⌈n 2⌉(z) = gyS(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 gxS(z) = Mn(x) = 1 ⇔ones(x)⩾ln 2m⇔ones(xS) + ones(z)⩾ln 2m In order to obtain the value of the entanglement, we will prove first the following statements: 2Note that the XOR function satisfies a⊕c=b⊕c⇐⇒ a=b,∀a, b, c ∈Z2. 36 Chapter 5. Entanglement ones(xS) = ones(yS)⇒ ∀z∈Z⌈n 2⌉ 2, gxS(z) = gyS(z) ones(xS)=ones(yS)⇒ ∃z0∈Z⌈n 2⌉ 2, gxS(z0)=gyS(z0) The first one is immediate. Let xS, yS∈Z⌊n 2⌋ 2such that ones(xS) = ones(yS). Then, for z∈Z⌈n 2⌉ 2, gxS(z) = 1 ⇔ones(xS) + ones(z)⩾ln 2m⇔ones(yS) + ones(z)⩾ln 2m⇔gyS(z) = 1 Let’s prove the second one. We can take, w.l.o.g., xS, yS∈Z⌊n 2⌋ 2such that ones(xS)> ones(yS). Let z0∈Z⌈n 2⌉ 2such that ones(xS) + ones(z0) = n 2. Then, ones(yS) + ones(z0)< ones(xS) + ones(z0) = ln 2m so gxS(z0)=1= 0 = gyS(z0) We have proven the only cases where the gxSfunctions are different happen when ones(xS) varies. Since |S|=n 2,ones(xS)∈ {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. 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, experimentally, 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.1We will compare these functions with others from a set of equal size2that 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 potentially 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 nrises. 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, considering 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, although 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 another 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 versions, 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 Frepresents all the analyzed functions and Drepresents the functions in dataset. Note that the denominator can be 0, indicating there does not exist a function in Fsatisfying 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.011.010.09.08.07.06.05.04.03.02.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.011.010.09.08.07.06.05.04.03.02.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.011.010.09.08.07.06.05.04.03.02.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 123456789101112 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. 123456789101112 0.0 0.1 0.2 0.3 0.4 0.5 Dataset Non dataset 6.3. Mitigating bias in Boolean circuits 59 45678910 10 20 30 40 50 60 pn Mn Pn P 0 n Cn C 0 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 nincreases than the growth of PRIMALITY. This is because the CLIQUE problem becomes more complex while the PRIMALITY problem becomes simpler as nincreases (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) x1AND x2is ALWAYS in level 1; ii) x3AND x4is 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 x1AND x2is 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 x1AND 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 x1AND x2, i.e., every gate of level two has the output of x1AND x2as 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). x1x2¯x2x4x1x3x4x5 As evident from the diagram, the gates influenced by the output of the gate x1AND 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. x1x2¯x2x4x1x3x4x5 6.3. Mitigating bias in Boolean circuits 61 As we can observe, by injecting the output of x1AND x2in 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 x1AND x2in 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 x1AND x2in a branch As we have introduced, these circuits keep x1AND x2in a certain branch and the rest of the circuit is formed (almost) randomly — keep in mind x3and x4are 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 x1AND 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 x1AND x2is 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 x3and x4during the upper levels, thereby augmenting the influence of {x3, x4}. Introducing ¬x1or ¬x2into 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 requirements 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, x2rather than x3, x4(as one gate is consistently added while the other is not). Hence, it becomes imperative to incorporate 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. 01234567891011 Depth 0 10 20 30 40 50 60 70 80 90 100 Percentage The bias decreases as the circuits grows deeper, as anticipated. In fact, there comes a point (around depth = 9) where x1, x2ceases to be predominant in half of the instances. 6.3.2. Poisoning the first level with x1AND x2 In this section, we will analyze the sample that contains the circuits in which every gate of the second level has x1AND x2as one of its inputs and never includes x3AND 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 x1AND x2will have an influence in most of them. We appreciate this in the following chart: 234567891011 Depth 0 10 20 30 40 50 60 70 80 90 100 Percentage 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 AC0class, 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 appears 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 entanglement. 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 cxSand 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 Akshould not be large. The ultimate goal would be to identify a certain invariant that evidences how the bias pattern becomes more complex as kgrows. Following the line of the first proposal and as a possible critique to the conjecture proposed, 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, PRIMALITY 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 determining 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 assumed. 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 concepts 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 concepts — 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 experiments 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 contributed 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 together 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 techniques 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 4and 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 6has 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.