Estudio de la endogamia de los circuitos booleanos

Estudio de la endogamia de los circuitos booleanos Research into the endogamy of boolean circuits Enrique Román Calvo DOBLE GRADO EN INGENIERÍA INFORMÁTICA - MATEMÁTICAS FACULTAD DE INFORMÁTICA UNIVERSIDAD COMPLUTENSE DE MADRID Trabajo de fin de grado - Curso 2019/2020 Fecha: 26 de junio de 2020 Directores: Narciso Martí Oliet Ismael Rodríguez Laguna Índice general Agradecimientos I Resumen III Abstract IV Introducción y motivación 1 Plan de trabajo 4 1. El espacio de circuitos 5 1.1. Definiciones previas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2. Representación minimal y maximal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3. Diversidad minimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.4. Orden lexicográfico de circuitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2. El algoritmo del índice 22 2.1. Resultados preliminares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.2. Índice y espacio cociente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3. Incremento del tipo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.4. La propiedad del buen prefijo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.5. Incremento del cableado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.6. Ampliación del suelo, cambio de nivel y fin del algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.7. Retorno a los circuitos: representante mínimo y circuito inicial . . . . . . . . . . . . . . . . . . . . . . 45 3. La endogamia de los circuitos 52 3.1. El problema de la endogamia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.2. Endogamia por representación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.3. Endogamias vectoriales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.4. Endogamia por colapso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.5. Umbral de colapso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4. Gramáticas y circuitos 62 4.1. Gramáticas libres de contexto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.2. Operadores no simétricos y el teorema de equivalencia . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5. Resultados y conclusiones 66 5.1. Implementación del algoritmo del índice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5.2. Información analizada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.3. Funciones alcanzadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.4. Análisis del λ-umbral.............................................. 70 5.5. Correlación entre las distintas métricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 5.6. Correlación entre las endogamias y número de puertas empleadas . . . . . . . . . . . . . . . . . . . . . 73 5.7. Correlación entre distintos datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 Conclusiones 79 Conclusions 81 Anexos 83 Anexo I: Gráficas de la sección 5.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 Anexo II: Gráficas de la sección 5.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 Anexo III: Gráficas de la sección 5.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 Anexo IV: Gráficas de la sección 5.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 Anexo V: Gráficas de la sección 5.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 Bibliografía 115 Agradecimientos Agradecer es sencillo, solo debes fingir ese sentimiento, más el sentimiento de agradecimiento no es fácil de fingir. Por ello, todo lo que bajo estas líneas se recoge es un reconocimiento explícito a aquellas personas sin las que este trabajo no hubiese salido adelante. Así, en primer lugar debo agradecer la infinita paciencia y el meticuloso trabajo de mis dos directores, Narciso Martí Oliet e Ismael Rodríguez Laguna, que me han ayudado y guiado de una manera excelente en el trabajo y han sido unos defensores a ultranza de este proyecto con auténtico fervor por lo que repetiría esta misma experiencia junto a ellos sin dudarlo si pudiera volver atrás. Uno de sus mayores logros ha sido el saber delegar a tiempo el asesoramiento en terceros cuando ha procedido. En concreto, quiero agradecer especialmente a Rubén Rafael Rubio Cuéllar por su disposición a ayudarme con aspectos técnicos de C++, Automake y Linux y a enseñarme cómo hacerlo de manera rápida y elegante a partes iguales; así como a Javier Rodríguez Laguna por dejarme usar una máquina virtual del Instituto de Física Teórica de la UAM para poder ejecutar los experimentos realizados. Además, quiero agradecer a mis padres el apoyo mostrado durante estos años de carrera, ya que de no ser por ellos, por su apoyo económico y emocional y los valores que me han transmitido no hubiera sido la persona que soy y no estaría hoy escribiendo estas líneas que estás leyendo. Por una parte, sin el apoyo de mis amigos no habría podido entregar en tiempo y forma este trabajo, me habría desesperado en el proceso. Así, por todas las imágenes no deseadas de manteles y espaguetis que habéis visto estos meses: Lucía, Isabel, Iván, Irene... gracias. Gracias inmensas a mis compañeros de clase, que partieron siendo eso y acabaron siendo mi vida; unos buenos y necesarios amigos que os recomiendo a todos encontrar alguna vez en vuestra vida. A todos y cada uno de ellos, gracias. Pero, sin dudar a dudas, debo agradecerle este trabajo a Francisco Bellot Rosado, gran matemático y gran persona que me ha dado grandes valores y amigos que son valores. María, Antonio, Ruth, Victoria... sois vosotros. Por otra parte, debo también agradecer a Carmen y María José que con su dedicación y su entusiasmo me demostraron que la docencia también puede ser vocacional y destacaron para mí de manera sobresaliente como profesoras en la etapa de educación obligatoria. Vocación que afortunadamente han demostrado la mayor parte de los profesores que en esta universidad me han impartido y eso verdaderamente se agradece. Desgraciadamente, también debo mencionar al XXI ENEM haberme consumido todo el tiempo libre que este trabajo me ha dejado, pero haberme brindado a su vez la oportunidad de conocer a gente maravillosa y muy trabajadora. Gracias chicos por este congreso que casi hicimos pero no pudo ser. I Y por último y más importante, quiero agradecerte a ti, lector, por no haber imprimido este documento y leerlo en su formato digital. Gracias por no malgastar papel de manera innecesaria. Y sobre todo y más importante, gracias por leerlo. II Resumen El objetivo de este trabajo consistió en desarrollar un experimento que permita analizar múltiples tipos de circuitos booleanos y las funciones que estos computan, de manera que podamos analizar las relaciones entre ambos conceptos. En el primer capítulo, se expone una definición formal del concepto archiconocido de circuito booleano, se analiza el crecimiento doblemente exponencial del conjunto de circuitos con mbits de entrada y se dota de un orden total a dicho conjunto. En el segundo capítulo, se demuestran una serie de resultados sobre vectores con determinadas propiedades que nos permiten recorrer de manera eficiente el conjunto de circuitos booleanos que tienen determinada profundidad y anchura. Este algoritmo se ha implementado en C++ utilizando técnicas de programación concurrente y estructuras de datos adecuadas para garantizar la eficiencia del mismo. A lo largo del tercer capítulo se exponen distintas métricas para medir la endogamia de los circuitos booleanos, así como intuiciones que justifican estas definiciones. Además, se incorpora un breve cuarto capítulo que versa sobre un tipo de gramática libre de contexto particular que genera funciones booleanas y su correspondencia con los circuitos booleanos. Finalmente, este trabajo concluye con un quinto y último capítulo en el que se analizan los resultados obtenidos en este experimento y se exponen las conclusiones consecuentes. Palabras clave: Complejidad de circuitos. Circuito booleano. Endogamia de un circuito. Función booleana. Índice de un circuito. P/poly. Propiedad del buen prefijo. Clase de complejidad. Algoritmo del índice. Correlación entre funciones y circuitos. III Abstract The aim of this project was to develop an experiment that allow us to analyze different kinds of boolean circuits and the functions they compute to study the relationship between both concepts. In the first chapter, a formal definition of boolean circuits is introduced, the double exponential growth of the set of circuits with mbits of input is analyzed and a total order in this set is defined. During the second chapter, some results about vectors of some kind are proved, which allow us to efficiently sweep the set of boolean circuits with fixed depth and width. This algorithm has been implemented in C++ using concurrent programming and adequate data structures to ensure its efficiency. During the third chapter, some metrics to measure the endogamy of boolean circuits are defined and some ideas beyond these definitions are added. In addition, there is a fourth brief chapter where the relationship between a special type of context-free grammar and its equivalence with our boolean circuits are discussed. To conclude, a final fifth chapter is added to analyse the results obtained in the experiment and the conclusions these results led us to. Keywords: Circuit complexity. Boolean circuit. Endogamy of a circuit. Boolean function. Index of a circuit. P/poly. Good prefix property. Complexity class. Index algorithm. Correlation between functions and circuits. IV Introducción y motivación Cuando uno se pregunta para qué sirve estudiar un circuito formado por puertas lógicas, lo primero que se le viene a la cabeza es toda la teoría de la arquitectura de computadores que nos dice que, en esencia, un computador es un conjunto de puertas lógicas conectadas entre sí. Así, el estudio de los mismos puede proporcionar importantes mejoras en el rendimiento de nuestros computadores. Por ejemplo, ese es el caso de los grafos and-inversor; una manera de modelizar los circuitos lógicos que es útil en distintos contextos relacionados con el hardware como en el expuesto en este artículo [1]. Sin embargo, no será ese el camino que tomemos en este documento. Imaginemos por un momento un circuito lógico formado por puertas and, or de dos entradas y not de una entrada en el que no hay retroalimentación, es decir, es un circuito puramente combinacional; el cual está conectado aninputs. Dicho circuito, dependiendo de cuál sea el valor de su entrada, devuelve una salida binaria, 0o1. Además, es claro que hay 2ncombinaciones de valores distintos que pueden tomar los ninputs: cada uno de ellos solo puede tomar el valor >o el valor ⊥. Así, podemos representar una función booleana con 2nbits, cada uno de ellos asociado a la evaluación de la función en cada uno de las combinaciones de valores que los inputs pueden tomar. Por otra parte, es claro que toda función es computable con un circuito booleano: nos basta para cada conjunto de valores del input que den 1realizar el and de los mismos y luego juntarlos todos con un or. Pero... ¿cuántas de estas funciones son computadas con un circuito que utilice un número de puertas polinómico en n? Eso ya no es tan sencillo de averiguar. Tal y como se exhibe en el libro Computational Complexity - A Modern Approach [2], para cada valor de nexiste alguna función booleana que no es computable por ningún circuito de tamaño 2n 10n. De hecho, la gran mayoría de dichas funciones no son computables por ningún circuito de tamaño polinómico, ya que, siendo pel polinomio que acota el número de puertas del circuito, el número de circuitos posibles está en O(p0(n)p(n)(siendo p0=kp con kconstante), mientras que el número de funciones posibles está en O(22n). Así, de manera natural, surge preguntarse qué funciones no son computables con circuitos con un número de puertas polinómico. La respuesta a esta pregunta es una gran incógnita en el campo de la informática teórica. Expongamos brevemente las implicaciones que dicha respuesta tendría sobre el resto de campos de la informática, y por extensión, sobre nuestra vida diaria. Denotamos por Pa la clase de complejidad formada por el conjunto de problemas de decisión que pueden ser resueltos en tiempo polinómico por una máquina de Turing determinista y denotamos por NP al conjunto de problemas de decisión que pueden ser resueltos en tiempo polinómico por una máquina de Turing no determinista. Así, 1 el famoso problema P vs NP se pregunta si P(NP. Este problema es famoso por su dificultad (no en vano es uno de los problemas del millón de dólares [3]) y por la revolución científica que conllevaría P=NP. ¿Qué tiene que ver pues P vs NP con los circuitos booleanos? En primer lugar, notemos que se define la clase de complejidad P/poly como el conjunto de lenguajes computables por una familia de circuitos booleanos de tamaño polinómico, uno por cada tamaño de entrada. Así, un resultado conocido [2] es que P(P/P oly. Por tanto, cualquier problema que no pueda resolverse con una familia de circuitos de tamaño polinómicos no podrá estar en P. Es por ello que entender qué problemas requieren familias de circuitos de gran tamaño para ser computados abriría una nueva vía para abordar distintos problemas abiertos en el ámbito de la complejidad; como el ya mencionado P vs NP. Sin embargo, nuestra meta será mucho menos ambiciosa, pues nos limitaremos a buscar qué factores influyen en el tamaño de los circuitos que computan una función booleana. Para ello, el enfoque que hemos tomado es el siguiente: en un circuito booleano irredundante, es decir, en el que existe un camino entre la puerta de salida y todas las demás puertas, si la anchura del mismo está limitada, en general habrá un nivel en el que las puertas se reutilizan, es decir, hay dos puertas que tienen como uno de sus inputs una misma tercera puerta. A esta situación la denominamos endogámica, ya que hay una fuerte dependencia entre las puertas de un nivel y las de su nivel inferior. Así, parece razonable preguntarse si esta reutilización reiterada de puertas coarta la expresividad del circuito y genera, en consecuencia, funciones calculadas por otros circuitos más pequeños. Haciendo una analogía con el caso del árbol genealógico, la endogamia en un circuito booleano sería equiparable a la endogamia en una familia en la que, por ejemplo, los padres de un hijo sean hermanos, primos, primos segundos... Desgraciadamente, las causas y los efectos de estas relaciones nos son desconocidos, por lo que navegar en el mar de la endogamia es un viaje a ciegas que quizás aporte resultados interesantes o quizás encallemos a medio camino. Por ello, se ha diseñado un experimento para tratar de medir este fenómeno. En primer lugar, se generan de manera exhaustiva circuitos con profundidad y anchura fijas, incrementándose ambas paulatinamente. Así, computando la función booleana asociada al mismo, podemos guardar en una tabla indexada por la función computada el menor circuito computado (por ejemplo, menor número de puertas, menor profundidad...). Aún a pesar de la dispersión que de dicha tabla se espera, por los resultados del libro Computational Complexity - A Modern Approach mencionados anteriormente, elegir tamaños de input excesivamente grandes convierten en un cuello de botella la representación de las funciones computadas. Por ello, se ha optado por tomar 5bits de input, de manera que el número máximo de funciones obtenibles con este experimento es de 225= 232, que coincide con el máximo número de enteros representables en la mayoría de lenguajes de programación. Tras la ejecución del mismo, tenemos por una parte información del tamaño y estructura de un circuito que computa dicha función, así como información de aquellas funciones que no aparezcan en dicha tabla: requieren circuitos con profundidad o anchura mayores de lo considerado. Por ello, la información obtenida del mismo no es baladí: puede servirnos para obtener evidencia empírica del fenómeno de la endogamia. Esta evidencia trataremos de ponerla de relieve mediante el análisis de distintas variables aleatorias y la correlación existente entre las mismas. Además, otro fenómeno relacionado con las funciones booleanas es el de la repetitividad de patrones en la secuencia de bits que definen esta función. Este fenómeno, más etéreo, consiste en la existencia de una relación indeterminada entre la complejidad en el patrón de una función booleana 2 Además, hagamos notar lo siguiente: al ser las puertas lógicas operadores simétricos, las tuplas (P, C1, C2)y(P, C2, C1)se comportan igual ante la evaluación y ante identidad y no tiene mucho sentido considerarlos distintos ya que en la idea intuitiva que hay por detrás de circuito físico se da que son exactamente iguales. Por ello, y durante del resto del documento, trabajaremos módulo simetría de los operadores. Es decir, se hablará indistintamente del circuito C:=P(C1, C2)o de C:=P(C2, C1)pero no se dirá que C:=P(C1, C2)sea igual que C0:=P(C1, C2). Lema 1.1.19. Si C1yC2son dos circuitos idénticos, ev#(C1) = ev#(C2). Demostración. Razonemos por inducción. Si C1yC2son dos circuitos de profundidad 0, entonces, por definición, son iguales. Luego solo puede suceder que ev#(C1) = ev#(C2). Supongamos que para cualesquiera dos circuitos de profundidad nse cumple el lema y sea C=P(C1, C2),C0= P0(C0 1, C0 2). Como C≡C0, entonces P=P0y, o bien C1≡C0 1, C2≡C0 2, o bien C1≡C0 2, C2≡C0 1. Por tanto ev#(C) = (ev#◦P)(C1, C2) = eq(P)(ev#(C1), ev#(C2)) = eq(P)(ev#(C0 1), ev#(C0 2)) = (ev#◦P)(C0 1, C0 2) = ev#(C0), donde se ha aplicado la hipótesis de inducción junto a la simetría de la puerta para garantizar que eq(P)(ev#(C1), ev#(C2)) = eq(P)(ev#(C0 1), ev#(C0 2)). A partir de ahora consideremos las puertas lógicas pertenecientes al conjunto P={∧,∨, id} definidas así: C:=∧(C1, C2)si C16=C2 C:=∨(C1, C2)si C16=C2 C:=id(C1, C2)si C1=C2 donde C1yC2son dos circuitos de la misma profundidad, la igualdad no es vía renombramiento y dichas puertas tienen un equivalente natural, el and y el or lógico de nvariables y la función identidad respectivamente. C1C2 Figura 1.1: Representación física del circuito C:=∧(C1, C2). C1C2 Figura 1.2: Representación física del circuito C:=∨(C1, C2). C1 Figura 1.3: Representación física del circuito C:=id(C1, C1). Para poder hablar de la evaluación de los circuitos con las puertas elegidas, necesitamos dotar aCde un m-polinomizador, donde mes el número de inputs. Aunque hay infinitas aplicaciones de esta naturaleza, mostraremos a continuación una manera natural de hacerlo. Lema 1.1.20. El espacio Ctiene un m-polinomizador compatible con la biyección entre polinomios xiy circuitos de profundidad 0, al cual llamaremos m-polinomizador usual. Demostración. Si Ces un circuito de profundidad 0, es equivalente a un polinomio xi, con lo que de manera natural asociaremos Ccon xi. Además, a circuitos idénticos asocia polinomios iguales, 9 lo cual es importante. Supongamos pues que tenemos el m-polinomizador usual definido para todo circuito de profundidad nde manera que circuitos idénticos tengan misma imagen y tomemos un circuito C:=P(C1, C2)de profundidad n+ 1. Entonces tenemos tres posibilidades: P=id. En este caso diremos que f(C0) = f(C1)2, ya que f(C1) = f(C2). P=∨. En este caso definiremos f(C0) = f(C1) + f(C2). P=∨. Así, tomaremos f(C0) = f(C1)·f(C2). Finalmente, es inmediato comprobar que circuitos idénticos tienen misma imagen gracias a la conmutatividad del anillo F2[x1, ..., xm]. Corolario 1.1.21. Todo circuito de profundidad ntiene asociado un polinomio de multigrado n. Demostración. Es inmediato debido a la construcción del m-polinomizador usual. Lema 1.1.22. Sean C1,C2yC3tres circuitos de profundidad ntales que C1≡C2yC16=C2. Entonces (ev#◦∧)(C1, C2)=(ev#◦∨)(C1, C2)=(ev#◦id)(C1, C1)y(ev#◦P)(C1, C3)=(ev#◦ P)(C2, C3), donde Pes una puerta lógica. Demostración. Si C1≡C2entonces se da que ev#(C1) = ev#(C2)por el lema 1.1.19. Así, utilizando las propiedades del equivalente, es claro que eq(∧)(ev#(C1), ev#(C2)) = eq(id)(ev#(C1), ev#(C1)) = eq(∨)(ev#(C1), ev#(C2)); ya que el or y el and lógicos aplicados a la misma tupla se comportan como la identidad. De este modo, la primera parte del lema queda probada. Finalmente, es inmediato concluir la última parte puesto que (ev#◦P)(C1, C3) = eq(P)(ev#(C1), ev#(C3)) = eq(P)(ev#(C2), ev#(C3)) = (ev#◦P)(C1, C3). Este lema junto al 1.1.19 nos hace ver que los circuitos idénticos, aun no siendo iguales, son intercambiables gracias siempre a los equivalentes naturales que hemos elegido. Esto propiciará más adelante que tratemos de evitar repeticiones dentro de las ecuaciones de un circuito, las cuales serán generadas debido a la presencia de dichos circuitos idénticos. Por otra parte, al lector avezado no se le habrá escapado la ausencia en esta elección de puertas lógicas negadoras. Esto se debe al siguiente resultado: Teorema 1.1.23. Todo circuito lógico generado por las puertas ∧,∨, id y¬tiene un circuito lógico equivalente donde todos los ¬se encuentren en el nivel de profundidad 0. Demostración. En primer lugar, observemos que todos los ¬se pueden ver como un añadido a las puertas ∧,∨eid, es decir, ¬◦∧,¬◦∨y¬◦ id. Así, dado un circuito arbitrario, podemos considerar que los ¬solo siguen a una puerta lógica de la manera explicada. 10 Razonemos una vez más por inducción. Si el circuito lógico tiene profundidad 0, es inmediato. Así, supongámoslo cierto para el nivel ny tomemos un circuito de profundidad n+ 1 definido así: C0:=P(C1, C2). Si P∈ {∧,∨, id}, ya habríamos acabado. Por ello, supongamos que P∈ {¬◦∧,¬◦∨,¬◦ id}. En ese caso, podemos definir un circuito C0:=P0(¬(C1),¬(C2)), donde P0=Qsi P=¬◦ Q; el cual es equivalente a C. Por hipótesis de inducción, existe un circuito C00 equivalente a C0donde todos los ¬están en el nivel 0. Por tanto, al ser Cequivalente a C0, queda acabada la prueba. La utilidad de este teorema radica en lo siguiente: dado un circuito arbitrario Ccon kinputs generado por ∧,∨, id, lo podemos representar como un circuito con m= 2kinputs, donde los primeros kinputs los identificaremos con (x0, ..., xk−1)y los ksiguientes con (1 −x0, ..., 1−xk−1) (equivalentes a ¬(xi)). Por ello, podemos olvidarnos de las puertas ¬y suponer de ahora en adelante que el tamaño del input viene dado por m= 2k. Sin embargo, los resultados que se expondrán no lo tendrán en cuenta, es decir, solo influirán estas relaciones a la hora de evaluar el circuito, no de construirlo. 1.2. Representación minimal y maximal En esta sección mostraremos cómo transformar un circuito Cen otro C0de misma profundidad apoyándonos en la existencia de circuitos idénticos. Algoritmo 1.2.1 (Transformación minimal).Dado un circuito Cde profundidad ndevuelve un circuito C0de la misma profundidad que no tiene dos subcircuitos idénticos. Además, C0es único salvo renombramiento. Demostración. La idea de este algoritmo será ir construyendo una colección de circuitos Ci,0≤ i < n identificando circuitos idénticos, y esto lo haremos por inducción cambiando el mapa fi+1 en cada paso si fuese necesario. Todo circuito Cno tiene circuitos de profundidad 0idénticos por construcción, con lo que tomemos C0=C. Así, supongamos que tenemos definido Ck−1y que en E(Ck−1)no hay dos circuitos de profundidad j, 0≤j≤k−1idénticos. Construyamos pues un circuito Cksin circuitos idénticos de profundidad j, 0≤j≤k < n. Si no tiene dos subcircuitos de profundidad kidénticos, hemos acabado y Ck+1 =Ck. En caso contrario, sean D, D0@kCk−1de manera que D≡D0. Entonces, para todo circuito de la forma E:=P0(D0,ˆ D0), con D06≡ ˆ D0, D0≡Dredefinamos fk+1(E) = (P0, D, ˆ D0). Por otra parte, para todo circuito E:=P0(D0ˆ D0)con D0≡ˆ D0≡D, redefinamos fk+1(E) = (id, D, D). Finalmente denotemos por C0 kal circuito de profundidad ncon etiqueta Cdefinido con el nuevo mapa. El circuito C0 k−1obtenido con esta nueva colección de mapas cumple que tiene un circuito de profundidad kmenos y por tanto, menos pares de circuitos de profundidad kidénticos entre sí. Si este proceso lo repetimos para todos los circuitos de profundidad kde manera iterada obtenemos 11 un mapa modificado, fk+1, de manera que en el circuito resultante no hay subcircuitos idénticos de profundidad k. Así, tenemos perfectamente definido Cky en consecuencia, por inducción, Cn=C0. Finalmente el además es inmediato a la vista de la demostración: otra elección del circuito Da la hora de modificar el mapa fknos conduce a un circuito C00 que es un renombramiento de C0. Definición 1.2.2. Diremos que un circuito Cestá en su representación minimal si es idéntico al circuito C0obtenido al aplicar el algoritmo 1.2.1 al circuito C. Intuitivamente, la representación minimal de un circuito consiste en expresar dicho circuito con el menor número de puertas manteniendo la misma estructura, eliminando puertas repetidas. Sin embargo, destaquemos que esto no significa que el circuito que computa f(C)sea mínimo, donde fes el operador m-polinomizador usual. A mayores, destaquemos que esta representación minimal es única ya que el algoritmo anterior es determinista. Corolario 1.2.3. Para todo circuito Cy su representación minimal C0se da que ev#(C) = ev#(C0). Demostración. Es inmediato siguiendo la demostración del algoritmo 1.2.1 y aplicando sucesivamente los lemas 1.1.19 y1.1.22. Sin embargo, no es cierto que un circuito y la representación minimal de dicho circuito sean idénticos, como se puede ver en el siguiente ejemplo. Ejemplo 1.2.4. Sean los circuitos CyC0dados por las siguientes ecuaciones: E(C) = (C:=∧(D1, D2) D1:=id(in0, in0)D2:=id(in0, in0)(1.2) E(C0) = (C0:=id(D0, D0) D0:=id(in0, in0)(1.3) Es claro que C0es la representación minimal de Cpero C6≡ C0ya que C:=∧(D1, D2),C0:= id(D0, D0)y∧ 6=id. Intuitivamente esto es razonable ya que no es lo mismo crear un circuito usando dos puertas lógicas que usando tres. Pero sin embargo, es claro que son esencialmente el mismo circuito eliminando puertas redundantes, por lo que ampliaremos la definición de circuitos idénticos diciendo que dos circuitos son idénticos si sus representaciones minimales son idénticas. Algoritmo 1.2.5 (Transformación maximal).Dado un circuito Cde profundidad ndevuelve un circuito C0de la misma profundidad con 2n−1puertas. Demostración. La idea de este algoritmo será ir construyendo una colección de circuitos Ci, p ≤i≤ 2n−1, con p=|E(C)|, de manera que se dividan duplicidades para que florezcan circuitos idénticos y en cada paso aparezca una nueva puerta más; y esto lo haremos por inducción cambiando quizás 12 algún mapa de etiquetas en cada paso si fuese necesario. Dado que p=|E(C)|, tomemos Cp=C. Así, supongamos que tenemos definido Ck−1, p ≤k−1< n y que |E(Ck−1)|=k−1y generemos Ck. Si k−1< n implica que hay al menos una etiqueta Dutilizada dos veces asociada a un circuito de profundidad l > 0. Sea además D0una etiqueta no utilizada por ningún subcircuito de profundidad lde C. Así, si existe un circuito de profundidad l+ 1 definido como E:=id(D, D), y ampliemos la definición de fldiciendo fl(D0) = fl(D)y modifiquemos la definición de fl+1(E) = (P, D, D0), donde P∈ {∧,∨} y esta puerta se elige de manera arbitraria. Si no, es porque existen dos circuitos E, E0vl+1 Cdefinidos así: E:=P(D, C1), E0:=P0(D, C2), donde necesariamente P, P0∈ {∧,∨}. En este caso definamos fl(D0) = fl(D)y modifiquemos las definiciones de E, E0así: fl+1(E) = (P, D, C1), fl+1(E0)=(P0, D0, C2). En cualquiera de los dos casos el número de puertas ha aumentado en 1, con lo que podemos denotar por Ckal circuito de profundidad ncon etiqueta Cdefinido con el nuevo mapa. En este caso se da que |E(Ck)|=k, con lo que en un número finito de pasos hemos acabado. Definición 1.2.6. Diremos que un circuito Cde profundidad nestá en una representación maximal si es idéntico a alguno de los circuitos C0posibles que se pueden obtener a partir de Ccon el algoritmo 1.2.5. Corolario 1.2.7. La representación maximal de un circuito puede no ser única. Demostración. Se sigue del hecho de que en el algoritmo 1.2.5 si existe un circuito de la forma E:=id(D, D)lo podemos sustituir por E:=∧(D, D0)o por E:=∨(D, D0)de manera indistinta y los circuitos obtenidos son distintos (y no idénticos). Corolario 1.2.8. Si la representación minimal de un circuito Cde profundidad ntiene 2n−1 puertas, la representación maximal es única y coincide con la representación minimal. Demostración. En primer lugar, por el lema 1.1.16 todo circuito tiene a lo sumo 2n−1. Entonces, dado que la representación minimal es única y tiene 2n−1puertas, el algoritmo 1.2.5 devuelve un circuito idéntico a C. Corolario 1.2.9. La representación maximal de un circuito Cpuede ser única y no coincidir con su representación minimal. Demostración. Sea el circuito Cdefinido por las ecuaciones: E(C) =      C:=∧(D0, D1) D0:=∨(E0, E2)D1:=∧(E1, E2) E0:=id(in0, in0)E1:=id(in1, in1)E2:=id(in2, in2) (1.4) 13 Es claro que no está en representación maximal ya que |E(C)|= 6 6=7=23−1. Esto se debe a que la etiqueta E2se utiliza dos veces en las definiciones. Sin embargo, su representación maximal es única ya que solo hay una manera de definir una etiqueta E3y modificar la definición de f2(D1), a saber: E(C0) =      C0:=∧(D0, D1) D0:=∨(E0, E2)D1:=∧(E1, E3) E0:=id(in0, in0)E1:=id(in1, in1)E2:=id(in2, in2)E3:=id(in2, in2) (1.5) A partir de esta sección trabajaremos con circuitos en representación minimal, en los cuales se cumple que los términos identidad e igualdad son equivalentes. Todos los resultados los expondremos módulo identidad de circuitos, es decir, dos circuitos con la misma representación se considerarán el mismo. Además, los símbolos CnyCse emplearán para el conjunto de circuitos en representación minimal de profundidad ny el conjunto de circuitos en representación minimal de profundidad arbitraria respectivamente. 1.3. Diversidad minimal Analizaremos ahora la diversidad de circuitos de profundidad nque se pueden generar a partir de dos de profundidad n−1. Definición 1.3.1. Denotamos por δm∈N→Na la función diversidad definida por: δm(n) = m2n(1.6) Lema 1.3.2. Si el número de circuitos de profundidad nes k, entonces el número de circuitos de profundidad n+ 1 es k2. Demostración. Como el operador ∧solo se aplica sobre circuitos distintos de Cny en Cnhay k circuitos, entonces el número de ternas (∧, C1, C2), con C16=C2es k 2=1 2k·(k−1) (donde el factor 1 2aparece por la simetría del operador). De manera análoga, el número de ternas (∨, C1, C2) es 1 2k·(k−1). Por último, como el operador identidad se aplica solo a circuitos idénticos, y hay k circuitos en Cn, obtenemos que en Cn+1 hay 2·1 2k·(k−1) + k=k2. Corolario 1.3.3. El número de circuitos de profundidad ngenerables a partir de minputs es δm(n). Demostración. Si n= 0, los únicos circuitos que se pueden generar son todos aquellos que están en Im, y |Im|=m=δm(0). Supongamos ahora que hemos probado el corolario para n, es decir, hay δm(n)circuitos en Cn. Entonces por el lema 1.3.2 en Cn+1 hay δ2 m(n) = δm(n+ 1) circuitos. 14 Como se puede ver, el número de circuitos crece de manera doblemente exponencial con la profundidad. Este resultado es importante ya que nos dice que este espacio es inabarcable de manera práctica, solo para m= 1 es computable dicho espacio (el cual es trivial). Además, esto justifica el porqué a la hora de razonar sobre complejidad de problemas en el que intervengan circuitos se exija que la profundidad pde dichos circuitos venga dada por una función logarítmica (p∈ O(log(n))), de manera que |Cp|=δm(log(n)) = mn. De esta manera, estaríamos trabajando sobre un espacio de tamaño exponencial, no doblemente exponencial, lo que puede aliviar la dificultad del problema con el que estemos trabajando. 1.4. Orden lexicográfico de circuitos Finalizaremos este capítulo mencionando un orden total que podemos inducir en el espacio de circuitos C. Este orden obtenido será la guía del algoritmo presentado en el capítulo 2, el cual se encargará de recorrer Caprovechando distintas propiedades de este orden lexicográfico. En primer lugar, establezcamos un orden en el conjunto de inputs, esto es, digamos a partir de ahora que x0< ... < xm−1. Así, hemos dotado de un orden a los circuitos de profundidad 0. Veamos que, solo del hecho de establecer un orden entre las puertas lógicas, se dota de manera natural de un orden a este conjunto. Definición 1.4.1. Dado un circuito Cde profundidad ny una función f:Cn→Z|Cn|, denominamos índice de Cvía fal valor f(C). A dicha función fla denominaremos función índice y la denotaremos por fn, donde nes la profundidad del circuito sobre el que se aplica. Definición 1.4.2. Dadas dos puertas lógicas P, P0decimos que Pes menor que P0si se da que para cualesquiera circuitos C1,C2de profundidad n,P(C1, C2)< P0(C1, C2). Así, dado un conjunto de puertas lógicas diremos que están ordenadas si dadas dos puertas P,P0o bien P < P0o bien P0< P. En nuestro caso podemos establecer que ∨<∧, pero no podemos comparar ninguna de ellas con la identidad. En cualquier caso, ya que podemos ver id como una extensión de ∧, abusaremos de este concepto y diremos que existe un orden entre las puertas, eso es, que ∨<∧ ≡ id. Esta decisión arbitraria, ya que podíamos haber visto id como una extensión del operador ∨, no tendrá a posteriori mucha influencia; simplemente se toma por el mero hecho de que queda extraño hablar de órdenes totales inducidos por conjuntos no comparables. Además, como se verá más adelante, solo usaremos este orden para desempatar entre circuitos distintos compuestos con los mismos argumentos (por lo que la decisión tomada sobre id no tendrá peso alguno). De manera natural, es claro que cualquier función índice induce un orden sobre Cncon el orden natural de Zδm(n). A este orden inducido lo denominaremos orden en el nivel n. Sin embargo, estas funciones no solo inducen un orden sobre Cnsino que también sobre Cn+1. Lema 1.4.3. Toda función índice fninduce un orden sobre Cn+1. Demostración. Sea fnuna función índice y sean C:=P(C1, C2),C0:=P0(C0 1, C0 2)dos circuitos de profundidad n+ 1 distintos. Entonces diremos que Ces menor que C0vía fnsi fn(C1)< fn(C0 1), 15 o bien fn(C1) = fn(C0 1)yfn(C2)< fn(C0 2), o bien fn(C1) = fn(C0 1), fn(C2) = fn(C0 2), P =∨y P0=∧. Este orden es total en Cnya que estamos trabajando sobre circuitos en representación minimal y por tanto identidad es sinónimo de igualdad. Sin embargo, este orden no dice nada sobre los circuitos de profundidad menor que n; y en consecuencia, no ordena internamente sus subcircuitos. Una idea naïf para extender esta definición podría ser intentar realizar un pequeño apaño al lema anterior en dirección contraria. Sin embargo, hacerlo así hace que al tomar dos circuitos de profundidad n > 2, el orden de los subcircuitos de profundidad n−2no está unívocamente determinado, esto es, puede darse que C6=C0,En−2(C) = En−2(C0)y el orden inducido sobre este subconjunto de circuitos de Cn−2sea distinto. Veámoslo con un ejemplo. Ejemplo 1.4.4. Sean los circuitos CyC0de profundidad n > 2que vienen dados por las ecuaciones: E(C) =      C:=∧(C1, C2) C1:=∧(D1, D2)C2:=id(D3, D3) D1:=id(E1, E1)D2:=∧(E1, E2)D3:=∧(E1, E3) (1.7) E(C0) =      C0:=∧(C0 1, C0 2) C0 1:=∧(D0 1, D0 2)C0 2:=id(D0 3, D0 3) D0 1:=id(E1, E1)D0 2:=∧(E1, E3)D0 3:=∧(E1, E2) (1.8) C C1C2 D1D2D3 E1E2E3 Figura 1.4: Representación física del circuito C. C0 C0 1C0 2 D0 1D0 2D0 3 E1E2E3 Figura 1.5: Representación física del circuito C0. donde se han omitido de E(C)yE(C0)las definiciones de E1, E2yE3y todos sus subcircuitos. En estas condiciones es claro que D1=D0 1, D2=D0 3yD3=D0 2. Y por tanto es fácil ver que el orden inducido de manera recursiva vía un conjunto de funciones índices que cumplen que D1< D2< D3 (y en consecuencia D0 1< D0 2< D0 3) sobre CyC0llevaría a que E1< E3< E2en el primer caso y que E1< E2< E3en el segundo. 16 Sin embargo, sería recomendable buscar unas funciones índices únivocamente determinadas para todos los niveles, de manera que dichas funciones interaccionen entre sí. Teorema 1.4.5. Para todo n∈Zexiste una función índice determinada unívocamente por el orden entre circuitos y el orden entre puertas. Demostración. En primer lugar, analicemos los circuitos de profundidad 0. Así, sea C:=inidonde 0≤i<mde dicha profundidad y definamos f0(C) = i. Por tanto, f0es una función índice basada en el orden entre circuitos. Supongamos que existe ahora fnen dichas condiciones, tratemos de definir fn+1. Así, dado C:=P(C1, C2), definamos fn+1(C) = δ2 m(n)−(δm(n)−fn(C1))2+ 2(fn(C2)−fn(C1)) −g(P), donde g(P)=1si P=∨y0en otro caso. La idea intuitiva de esta función se encuentra ilustrada en la figura 1.6. Veamos pues que fn+1 es biyectiva viendo que es sobreyectiva, ya que |Cn+1|= δm(n+ 1) <∞. En primer lugar, notemos que fn+1(∨(C1, C2)) + 1 = fn+1(∧(C1, C2)) y que si fn(C1) = 0, entonces P=id yfn+1(id(C1, C1)=0. Así, nuestro objetivo será construir una cadena de circuitos de profundidad n+ 1 tales que la diferencia de su evaluación vía fn+1 diste 1y de longitud δm(n+ 1). Es claro que probado esto, la suprayectividad queda probada, y por ende, la biyectividad. Supongamos que tenemos el circuito C:=P(C1, C2)yfn+1(C) = k. Si P=∨, entonces ∧(C1, C2) será el siguiente circuito de esta sucesión. Por tanto, solo queda analizar los circuitos de la forma C:=P(C1, C2), con P∈ {id, ∧}. Si fn(C2)< δm(n)−1, entonces sea C0 2el circuito de profundidad nque cumple que fn(C0 2) = fn(C2) + 1. Así, es fácil comprobar que fn+1(P(C1, C2)) + 1 = fn+1(∨(C1, C0 2)). En caso contrario, fn(C2) = δm(n)+1, ya que |Cn|=δm(n)yfnestá bien definida. Así, sea C0 1el circuito de profundidad nque cumple que fn(C0 1) = fn(C1)+1. Entonces fn+1(id(C0 1, C0 1)) = fn+1(C1, C2)+1. Finalmente, contemos el número de circuitos que intervienen. Por el procedimiento empleado, es claro que es resultante de combinar el circuito de índice fn(C)con todos los circuitos con índice mayor o igual que este. Por tanto, el cardinal de este conjunto es: δm(n)−1 P i=0 (2 ·(δm(n)−1−i) + 1) = 2δ2 m(n)−2δm(n)−1 P i=0 i−δm(n)=2δ2 m(n)−δm(n)(δm(n)−1) −δm(n) = δ2 m(n) = δm(n+ 1). En definitiva, gracias a que esta cadena tiene longitud δm(n+1), el índice de su circuito minimal es 0y la distancia entre dos elementos consecutivos es 1, es claro que fn+1 es sobreyectiva. 17 0 1 2 0 id 1 2 0 1 2 0 id ∨ 1 2 0 1 2 0 id ∨ 1∧ 2 0 1 2 0 id ∨ ∨ 1∧ 2 0 1 2 0 id ∨ ∨ 1∧ 2∧ 0 1 2 0 id ∨ ∨ 1∧id 2∧ 0 1 2 0 id ∨ ∨ 1∧id ∨ 2∧ 0 1 2 0 id ∨ ∨ 1∧id ∨ 2∧ ∧ 0 1 2 0 id ∨ ∨ 1∧id ∨ 2∧ ∧ id Figura 1.6: Visualización de la definición de índice f1cuando m= 3. Los números representan los valores de f0(C), C ∈ C|0y las flechas indican cuál es el siguiente circuito generado. Corolario 1.4.6. Dado k∈Zy una función índice ˆ fnsobre un subconjunto de S⊂ Cnde tamaño kexiste una función índice ˆ fn+1 sobre el conjunto T⊂ Cn+1 generable por Scompatible con fn. Demostración. Por el lema 1.3.2, en Thay k2. Así, sustituyendo Cn,Cn+1 yδm(n)por S, T yk respectivamente en la demostración del teorema 1.4.5 obtenemos la función ˆ fn+1(C) = k2−(k− ˆ fn(C1))2+ 2( ˆ fn(C2)−ˆ fn(C1)) −g(P), la cual es índice en T. Finalmente, es inmediato ver que si C < C0vía ˆ fn+1 entonces C < C0vía fn+1. Así, denotaremos a partir de ahora por Fn={f0, ..., fn}al conjunto formado por las primeras nfunciones índice calculadas en el teorema 1.4.5. Corolario 1.4.7. Sean fn, fn+1 ∈ Fn. El orden inducido por fnen Cn+1 coincide con el orden natural de fn+1. Demostración. Considérese la cadena obtenida en el teorema 1.4.5 para circuitos de profundidad n+ 1. Es inmediato comprobar que para cualesquiera dos circuitos consecutivos de dicha cadena, ambos cumplen que son menores según el orden inducido por fndescrito en el lema 1.4.3. Así, el orden inducido por fncoincide con el definido por fn+1. 18 Por otra parte, ya que r, l ytdefinen el circuito C, podemos realizar otra representación matricial del mismo. Esta representación la denominaremos representación matricial dispersa para diferenciarla de la utilizada en el ejemplo 1.4.12, que renombraremos como representación matricial compacta. Finalmente, denotemos de ahora en adelante ˆ fi,0≤i≤na las funciones índices de Cn,w que se inducen de manera natural por Fn. Ejemplo 2.1.13. Mostremos las diferentes representaciones de un circuito tomando m= 6, n = 4 yw= 3. C0,4 C0,3 C0,2C1,2 C0,1C1,1C2,1 in0in1 Figura 2.1: Representación física del circuito C.         (id, 0,0) (∨,0,1) (id, 0,0) (∨,1,2) (id, 0,0) (∨,0,1) (∧,0,1) (0) (1)         (a) Representación matricial compacta.         001 010 001120 001010011 0 1         (b) Representación matricial dispersa. Figura 2.2: Representación matricial del circuito C. 2.2. Índice y espacio cociente El objetivo en este apartado será analizar cómo, dado un circuito C, obtener un circuito C0tal que se parezca mucho a Cpero cuyo índice difiera en 1frente a C. Sin embargo, aunque podríamos definir la cadena de circuitos que cumple esta propiedad, no es lo que vamos a hacer por una simple razón: cambiar el cableado de un circuito es más costoso que cambiar el tipo de una puerta. Por tanto, vamos a diseñar un algoritmo que reduzca el número de cambios de cable que hay que hacer cumpliendo algunas propiedades esenciales. Definición 2.2.1. Denotaremos por E|d(C)al conjunto n S l=d El(C). Definición 2.2.2. Diremos que los circuitos CyC0están en la misma clase de equivalencia C|dsi existe un renombramiento entre E|d(C)yE|d(C0)y denotaremos por Cn,w|dal conjunto formado por todas estas clases. En otras palabras, E|d(C)consiste en restringir las ecuaciones que definen a Cquedándonos 25 con los dúltimos niveles y C|dconsistiría en los circuitos que tienen los mismos rniveles iguales. Veámoslo con un ejemplo: Ejemplo 2.2.3. Consideremos los circuitos con las siguientes representaciones matriciales:       010 010221 001111221 0 1 2       Figura 2.3: Representación matricial dispersa de C.       010 010221 010020120 0 1 2       Figura 2.4: Representación matricial dispersa de C0. Así, es claro que C|3=C0|3, C|2=C0|2pero C|16=C0|1(y en consecuencia C|06=C0|0); solo basta mirar fila a fila cada matriz para detectar esto.  Observemos que una clase C|dpuede estar contenida en Cn,w|dpero también en Cn,w0|d. Esto quiere decir que hay un circuito C0en Cn,w0de manera que C0|d=C|d, o lo que es lo mismo, que E|d(C) = E|d(C0). Así, hay que tener especial cuidado si se cambia de clase para garantizar que esta nueva clase tiene algún circuito contenido en Cn,w (y generable por minputs). Notemos ahora algunas relaciones interesantes. En primer lugar, las clases C|dse pueden ver como elementos de C|d+1 y la diferencia entre dos elementos de C|des solamente los vectores v= (l0,d, r0,d, ..., lp−1,d, rp−1,d)yg= (t0,d, ..., tp−1,d), donde p=|Ed(C)|. En otras palabras, la diferencia entre dos clases son las puertas y cables del nivel d, y esta información queda plenamente recogida en los vectores v, g. De esta manera, podemos denotar de manera cómoda un circuito con la tupla de valores (tj, lj, rj), la cual escribiremos como tj(lj, rj)para replicar la notación que habíamos seguido hasta ahora. A su vez, las clases de Cn,w|dse pueden agrupar entre aquellas que comparten el vector v. A estas clases las denotaremos ˆ C|d, al conjunto de las mismas la denotaremos ˆ Cn,w|dy diremos que ves el vector asociado a la misma. En consecuencia, tenemos el siguiente diagrama conmutativo, donde las funciones πconsisten en la proyección sobre el conjunto imagen. Cn,w|d+1 ˆ Cn,w|d+1 Cn,w|dˆ Cn,w|d π π π π Figura 2.5: Diagrama conmutativo entre los distintos conjuntos de clases. Finalmente, hagamos notar que si ˆ C|des una clase de ˆ Cn,w|d, el índice es un orden sobre el conjunto de elementos C|d∈ Cn,w|dque son miembros de ˆ Cdy, por otra parte induce un orden sobre los elementos de ˆ Cn,w|d. Por ello, vamos a aprovechar la función índice para recorrer Cn,w|d por partes y en cada parte seguir el orden del índice aunque globalmente no sea así. 26 2.3. Incremento del tipo Supongamos que estamos dentro de una clase ˆ C|d, donde p=|Ed(C)|yv= (l0, r0, ..., lp−1, rp−1) es el vector asociado a la clase. Proposición 2.3.1. Dado vvector asociado a ˆ C|d, el vector g= (t0, ..., tp)de la clase C|ddentro de ˆ C|dcumple las siguientes propiedades: Si lj=rj, entonces tj= 1,0≤j < p. Si lj=lj+1, rj=rj+1,0≤j < p −1, entonces tj= 0 ytj+1 = 1. Demostración. Si lj=rj, entonces la puerta asociada es id, con lo que tj= 1. Por otra parte, si lj=lj+1 yrj=rj+1, entonces no puede darse que lj=rjdebido a estar en representación minimal, ni que Pj=Pj+1, con lo que debido al índice obtenemos que Pj=∨yPj+1 =∧y esto demuestra inmediatamente la proposición. A los valores de tjdel vector de tipos gque no estén determinados por la proposición 2.3.1 los denominaremos tipos libres olibres, y los denotaremos en el siguiente algoritmo por τj. Además, tomaremos γ= (τ0, ..., τT)como el vector de tipos libres. Corolario 2.3.2 (Tipo mínimo).Sea C|dmínimo dentro de ˆ C|dy sea g= (t0, ..., tp)el vector de puertas asociado a C|d. Entonces γes el vector nulo. Demostración. La demostración es inmediata ya que cualquier otro valor de γharía que el índice de la clase C0|dcon dicho valor de γfuese mayor. Proposición 2.3.3. Dado vasociado a ˆ C|dy dado g= (t0, ..., tp−1)asociado a C|dtenemos la siguiente alternativa: O bien existe un único g0= (t0 0, ..., t0 p−1)asociado a otra clase C0|dcon mismo vector vtal que el índice inducido de C0|ddista 1del de C|d, O bien el índice inducido en C|ddentro de ˆ C|des máximo. Demostración. Sin pérdida de generalidad podemos quedarnos con el vector γ= (τ0, ...τT)ya que, por la proposición 2.3.1, los valores que no sean libres están determinados. Entonces, si vemos γ como un número en binario, es claro que el vector asociado al número γ+ 1 es el único vector que podría cumplir la primera alternativa. Además, para que γ+ 1 no esté bien definido tendría que darse que γ≡2T−1, y en este caso es claro que el índice de C|des máximo. Ejemplo 2.3.4. Mostraremos de una manera visual en qué se traduce la proposición 2.3.3. Se muestran en negro los elementos lj, rjde una clase C|n−3(supuesto que n > 3), así como los tipos 27 tjde C|n−2. Además, se muestran en rojo los elementos tjque no son libres, en ámbar los libres tal que su tipo es 1y en verde los que tienen tj= 0.       011 010121 010230241 030120121221231             011 010121 010230241 031120121221230       Figura 2.6: Obtención de C0|n−3a partir de C|n−3vía la proposición 2.3.3. Se puede ver que la clase C0|n−3obtenida preserva los valores de los tipos no libres, y con los libres se comporta como un contador binario. Además, el color ámbar otorgado a los tipos indica intuitivamente que dicho valor no es incrementable. Por tanto, el índice de la clase será máximo cuando no haya ningún tipo de color verde; no podremos avanzar. Algoritmo 2.3.5 (Incremento del tipo).Dado una clase C|dde ˆ Ckcon vector asociado g, devuelve la clase C0|dcuyo vector asociado es g0y de índice 1mayor que el de C|do detecta que es imposible (y devuelve None). 28 Algoritmo 1 Incremento del tipo Require: g= [t0, ..., tp−1] j←p−1 while j≥0∧(tjno es libre ∨tj= 1) do if tjes libre then t0 j←0.Si es libre entonces tj= 1 y si existe g0,t0 j= 0. else t0 j←tj.Si no es libre y existe g0,t0 j=tj. end if j←j−1 end while if j=−1then return None . No existe g0. else t0 j←1.Existe g0yt0 jes libre, así que t0 j= 1. end if return g0= [t0, ...tj−1, t0 j, ..., t0 p−1] Demostración. La corrección de este algoritmo es inmediata gracias a la proposición 2.3.3. Como se puede ver, el algoritmo tiene un coste máximo de O(p), pero, por ser de facto un contador binario, el coste amortizado lo rebaja a O(T+ 1), donde Tes el número de libres en ˆ C|d. En definitiva, hemos conseguido recorrer la clase ˆ C|dincrementando en cada paso el vector tipo un poco, de ahí el nombre del algoritmo. 2.4. La propiedad del buen prefijo Nuestro siguiente objetivo será, fijada la clase ˆ C|d+1 recorrer las clases de ˆ Cn,w|dsiguiendo el orden del índice. Para ello nos valdremos de la propiedad del buen prefijo, la cual expondremos en esta sección. Así, supongamos que d > 0y denotemos p=|Ed(ˆ C)|yk=|Ed−1(ˆ C)|; y tomemos una clase ˆ C|dy su vector vasociado, el cual tiene tamaño 2p. Tengamos en cuenta que el objetivo de esta sección es buscar una clase ˆ C0|dtal que |Ed(ˆ C0)|=p,|Ed−1(ˆ C)|=kde manera que podamos pasar cómodamente de ˆ C|daˆ C0|d. Definición 2.4.1. Diremos que j∈Zes un valor válido si 0≤j < k. Definición 2.4.2. Dado un vector v0= (l0, r0, ...lj, rj)denotaremos por Sj,−1≤j < p al conjunto de restantes Sj=Zk\{li, ri|0≤i≤j}y denominaremos a v0el vector complemento de Sj. Intuitivamente, dada una colección de valores {l0, r0, ...lj−1, rj−1},Sjrepresenta los índices de los circuitos que faltan por añadir a un vector v0asociado a alguna clase ˆ C|kde manera que esté 29 bien formada, esto es, que utilice todos los circuitos del nivel inferior al menos una vez. Por ello, S−1={i|0≤i<k}ySp−1=∅. Normalmente, y mientras no se diga nada, tomaremos como vector complemento el vj= (l0, r0, ..., lj, rj), resultante de restringirnos a las 2(j+ 1) primeras componentes del vector vasociado a ˆ C|d. Lema 2.4.3. Si ves un vector de tamaño 2pasociado a una clase ˆ C|d, entonces Sp=∅. Demostración. Si Sp6=∅, entonces no puede estar asociado a ninguna clase de ˆ C|dya que en ese caso faltarían circuitos de Ed−1(ˆ C)por utilizar. Definición 2.4.4. Diremos que v0= (v0 0, ..., v0 r)es un prefijo de v= (v0, ..., vs), con r≤ssi v0 j=vj para todo 0≤j≤ry llamaremos número de huecos ah(v, v0) = s−r. Además, dado v= (v0, ..., vr)denotaremos por v+αal vector (v0, ..., vr, α). Lema 2.4.5 (Falta de huecos). 1. Si v0= (l0, r0, ...lj, rj)es un prefijo de vy si αes un valor válido tal que v0+αsea prefijo de un vector v00 de tamaño 2pasociado a alguna clase ˆ C0|d, entonces |Sj\{α}| ≤ h(v, v0+α). 2. Si v0= (l0, r0, ...lj, rj, lj+1)es un prefijo de vy si αes un valor válido tal que v0+αsea prefijo de un vector v00 de tamaño 2pasociado a una clase ˆ C0|d, entonces |Sj\{lj+1, α}| ≤ h(v, v0+α). Demostración. 1. Si se diese que |Sj\{α}| > h(v, v0+α), entonces de ninguna manera el vector v00 cumpliría que Sp=∅, lo cual contradiría el lema 2.4.3. 2. Análoga al apartado anterior. Lema 2.4.6 (Exceso de huecos).Sea v0= (l0, r0, ...lj, rj)un prefijo de vy sean λ≤ρdos valores válidos. Si v0+λ+ρes prefijo de un vector v00 de tamaño 2pasociado a alguna clase ˆ C0|d, entonces 2(k2−1−ˆ fn(ˆ C)) ≥h(v, v0+λ+ρ), donde ˆ C:=τ(λ, ρ)yτ= 1 si λ=ρy0en otro caso. Demostración. Por la proposición 2.1.4, solo hay k2−1−ˆ fn(ˆ C)circuitos generables a partir de los kexistentes que tengan índice mayor que ˆ C. Además, cada circuito emplea 2argumentos, con lo que el máximo número de valores que se pueden añadir al prefijo v0+λ+ρes 2(k2−1−ˆ fn(ˆ C)). Y este valor debe ser al menos h(v, v0+λ+ρ). Nótese que se toma τ= 0 si λ6=ρpara que el circuito 1(λ, ρ)pueda considerarse también. Tengamos en cuenta que el nombre de los lemas 2.4.5 y2.4.6 vienen dados por la negación de los mismos. Así, si no hay suficientes o hay demasiados huecos, es claro que al añadir los valores válidos no podemos obtener un vector v00 valido para alguna clase ˆ C|d. 30 Lema 2.4.7 (Test izquierdo).Sea v0= (l0, r0, ...lj, rj)un prefijo de vy sea λun valor válido. Si v0+λes prefijo de un vector v00 asociado a alguna clase ˆ C|dentonces o bien ˆ Sj=Sj\{λ}=∅o bien λ < m´ın{ˆ Sj}. Demostración. Si ˆ Sj6=∅, entonces sea ρ= m´ın ˆ Sj. Como λ6=ρ, entonces λ<ρ, ya que en caso contrario el circuito C:=P(C1, C2)tal que l=λ, r =ρcumpliría que l > r y entonces no estaría bien conectado; lo cual se contradice con las propiedades de nuestro conjunto Cn. Gracias a estos lemas, hemos podido apreciar propiedades que deben cumplir los valores λy ρcon los que queremos extender nuestro prefijo. Con los siguientes teoremas veremos que estas propiedades no solo son necesarias sino que también son suficientes. Teorema 2.4.8 (Propiedad del buen prefijo - derecho).Sea vel vector asociado a ˆ C|d, sea v0= (l0, r0, ..., lj+1)y sea ρ≥lj+1 un valor válido tal que 1(lj, rj)< τ(lj+1, ρ), con τ= 1 si lj+1 =ρy 0en otro caso. Entonces v0+ρes un prefijo de algún vector v00 asociado a alguna clase ˆ C0|dsi y solo si se dan las siguientes condiciones: |Sj\{lj+1, ρ}| ≤ h(v, v0+ρ). 2(k2−1−ˆ fn(τ(lj+1, ρ))) ≥h(v, v0+ρ), donde τ= 1 si lj+1 =ρy0en otro caso. Demostración. =⇒Es consecuencia inmediata de los lemas 2.4.5 y2.4.6. ⇐=Si 2(k2−1−ˆ fn(τ(lj+1, ρ))) ≥h(v, v0+lj+1 +ρ)entonces hay al menos una colección de valores V={li, ri|j+ 1 < i < p}ordenada vía el índice de manera que todos los circuitos de V sean distintos. Por otra parte, al ser v0asociado a v, se cumple que o bien Sj\{lj+1, ρ}es vacío o bien lj+1 <m´ın Sj\{lj+1}. Si es vacío, tomemos V0=Vy procedamos al el párrafo siguiente. Si no, ya que |Sj\{lj+1, ρ}| ≤ h(v, v0+ρ), podemos tomar los circuitos (si, si+1), si, si+1 ∈Sj, con Sjordenado vía el índice (tomando (si+1, si+1)en el caso de que sean impares) y sustituir estos cs =b1 2(|Sj\{lj+1, ρ}|+1)c circuitos por cualesquiera cs parejas de valores de Vobteniendo V0. De esta manera, ordenando V0vía el índice y tomando v00 =v0+ρ+V0, es claro que v00 está bien formado ya que a lo sumo hay un par de índices i, i + 1 tales que (li, ri) = (li+1, ri+1)para cada tupla (l, r)y utiliza todos los circuitos de Ed−1(ˆ C). En consecuencia, es un vector asociado a alguna clase ˆ C0|dyv0+ρes prefijo de él. Teorema 2.4.9 (Propiedad del buen prefijo - izquierdo).Sea vel vector asociado a ˆ C|d, sea v0= (l0, r0, ..., lj, rj), con j < p −1y sean λ, ρ valores válidos tales que λ≤ρy tales que 1(lj, rj)< τ(λ, ρ), con τ= 1 si λ=ρy0en otro caso. Entonces v0+λ+ρes un prefijo de algún vector v00 asociado a alguna clase ˆ C0|dsi y solo si se dan todas las condiciones siguientes: |Sj\{λ, ρ}| ≤ h(v, v0+λ+ρ). 31 2(k2−1−ˆ fn(τ(λ, ρ))) ≥h(v, v0+λ+ρ), donde τ= 1 si λ=ρy0en otro caso. O bien Sj\{λ}=∅, o bien λ≤m´ın Sj. Demostración. =⇒Es consecuencia inmediata de los lemas 2.4.5,2.4.6 y2.4.7. ⇐=Si 2(k2−1−ˆ fn(τ(λ, ρ))) ≥h(v, v0+λ+ρ)entonces hay al menos una colección de valores V={li, ri|j+ 1 < i < p}ordenada vía el índice de manera que todos los circuitos de Vsean distintos. Por otra parte, por la tercera condición, o bien Sj\{λ}=∅, o bien λ≤m´ın{Sj}. Así, definido Vy gracias a la tercera condición podemos proceder de manera análoga al teorema anterior para obtener un V0tal que v00 =v0+λ+ρ+V0sea un vector asociado a alguna clase ˆ C0|d y en consecuencia, v0+λ+ρes prefijo de v00. Corolario 2.4.10 (Mínimo ρ).En las condiciones del teorema 2.4.9, si h(v, v0+λ)>|Sj\{λ}|, podemos tomar ρ=λ. Si no, y supuesto que {s∈Sj|s>λ} 6=∅, el valor ρ= m´ın{s∈Sj|s > λ} satisface el teorema para dicho λ. Además, este ρes el mínimo valor obtenible que satisface el teorema para dicho valor de λ. Demostración. En primer lugar notemos que la tercera condición del teorema no se ve afectada por este resultado al no depender de ρ. Así, si h(v, v0+λ)>|Sj\{λ}|, entonces h(v, v0+λ+λ)≥ |Sj\{λ}|, lo cual equivale a la primera condición. Además, es claro que no hay menor ρque permita que τ(λ, ρ) esté bien conectado. Finalmente, por la definición del índice, la cota superior de los huecos cumple que 2(k2−1−ˆ fn(τ(λ, ρ))) ≤2(k2−1−ˆ fn(τ(λ, λ))). Es decir, si hay algún valor ρque posibilita que se cumpla el teorema para dicho v0y dicho λ, este debe ser ρ=λ. Sin embargo, si h(v, v0+λ)≤ |Sj\{λ}|, entonces no se cumple la primera condición con dicho ρ. De hecho, no se cumplirá para ningún ρque no esté en Sj\{λ}. Por ello, ρdebe estar en Sj\{λ}. Además, para que esté bien conectado, ρ≥λ, por lo que, utilizando la segunda condición de nuevo, en el caso de haber un ρque cumpla las condiciones del teorema para este λ,ρ= m´ın{s∈Sj|s > λ} las cumplirá, con lo que esta definición de ρlo hace mínimo. Notemos que si h(v, v0+λ)≤ |Sj\{λ}| y{s∈Sj|s > λ}=∅, entonces hemos probado además que el vector v0+λno es prefijo de ningún v00 asociado a alguna clase ˆ C0|d. Algoritmo 2.4.11 (Propiedad del buen prefijo).Dado v= (l0, r0, ..., lp−1, rp−1)vector de ˆ C|d,j entero tal que 0≤j < p,Sjyρoλsegún proceda, devuelve si v0= (l0, r0, ..., lj, rj, λ, ρ)cumple la propiedad de buen prefijo. 32 Algoritmo 2 Propiedad del buen prefijo Require: Sj, λ oρyh(v, v0). if λno es None then Comprobar el lema Test izquierdo .Si no se da, devuelve false. Obtener ρusando el corolario Mínimo ρ.Si no existe, toma el valor None. else λ←lj+1 .Si ρ<lj+1, toma el valor None. end if if λoρes None then return false else Comprobar los lemas Falta de huecos yExceso de huecos .Si no se dan, devuelve false. return true .Se cumplen todas las condiciones del buen prefijo. end if Demostración. La demostración se sigue de los teoremas 2.4.8,2.4.9 y del corolario 2.4.10. Nótese que dado j, el coste de obtener h(v, v0)suele ser constante en la mayoría de los lenguajes de programación. Así, suponiendo que Ses un conjunto implementado con un montículo que tenemos calculado previamente, el coste de validar los lemas 2.4.5 y2.4.7 está en O(log(p)) al igual que el coste del corolario 2.4.10. Finalmente, el coste de comprobar el lema 2.4.6 es constante, con lo que el coste de este algoritmo es del orden de O(log(p)). Recapitulando brevemente esta sección: dado un vector vasociado a una clase ˆ C|dy un valor λ(respectivamente ρ) hemos obtenido un test para saber si existe un prefijo de tamaño 2j (respectivamente 2j+ 1) de vde manera que también lo sea de un vector v0distinto. 2.5. Incremento del cableado Gracias a la propiedad del buen prefijo y dado un vector vasociado a una clase ˆ C|d, trataremos de obtener otro vector v0asociado a otra clase ˆ C0|dde manera que ˆ C|d+1 =ˆ C0|d+1. Además, mostraremos cómo poder hacerlo de manera que el índice entre ambas clases diste 1. En esta sección pondremos el foco en cómo obtener ˆ C0|dtal que |Ed(ˆ C)|=|Ed(ˆ C0)|=py|Ed−1(ˆ C)|= |Ed−1(ˆ C0)|=k, si esto es posible; donde pykse definen como en la sección anterior. Lema 2.5.1 (Siguiente derecho).Sea vr j= (l0, r0, ..., lj). Si ni ρ0=rj+ 1 ni ρ00 = m´ın{s∈ Sj−1|s>rj}(supuesto que {s∈Sj−1|s>rj} 6=∅) son valores válidos con los que se cumple la propiedad del buen prefijo, entonces no existe ningún ρ>rjque lo permita. Demostración. En primer lugar notemos que si rj+ 1 no es válido, no existe ρ>rjque sea válido, con lo que sin pérdida de generalidad supongamos que rj+ 1 es válido. Además, por ser vr jprefijo de v, se da que rj≥lj. 33 Así, razonemos por contradicción. Sea ρdistinto a ambos valores. Si ρ0no cumple las condiciones del teorema, es porque o bien 2(k2−1−ˆ fn(0(lj, ρ0))) < h(v, vr j+ρ0)o bien |Sj−1\ {lj, ρ0}| > h(v, vr j+ρ0). Si es porque se da que 2(k2−1−ˆ fn(0(lj, ρ0))) < h(v, vr j+ρ0), es claro que no existe ningún ρadmisible, ya que ˆ fn(0(lj, ρ0)) <ˆ fn(0(lj, ρ)) y en consecuencia el lema 2.4.6 no se cumplirá para ningún valor ρ. Por tanto, podemos suponer que lo que acontece es que |Sj−1\{lj, ρ0}| > h(v, vr j+ρ0). Así, para cualquier ρtal que |Sj−1\{lj, ρ}| =|Sj−1\{lj, ρ0}| se va a dar que |Sj−1\{lj, ρ}| > h(v, vr j+ρ); con lo que de existir dicho ρ, este tiene que estar en Sj−1\{lj}. Además, ρ>rj, con lo que debe estar en ˆ Sj−1={s∈Sj−1\{lj} | s > rj}. Si ˆ Sj−1=∅, hemos acabado la demostración. Si no, podemos tomar ρ00 como en el enunciado del teorema, y, ya que ρ≥ρ00 ≥ρ0, podemos razonar como en el párrafo anterior para deducir que debe darse que |Sj−1\ {lj, ρ00}| > h(v, vr j+ρ00)si existe dicho valor ρ. Así, ya que |Sj−1\{lj, ρ00}| =|ˆ Sj−1|+ 1 = |Sj−1\{lj, ρ}|, es claro que ρincumple el lema 2.4.5. Este resultado es muy importante ya que nos dice que dado v0de tamaño impar, solo nos basta con probar dos valores de ρpara ver si v0+ρes prefijo de un vector v00 asociado a alguna clase ˆ C0|d. Lema 2.5.2 (Siguiente izquierdo).Sea vl j= (l0, r0, ..., lj−1, rj−1). Si ni λ0=lj+1 ni λ00 = m´ın{s∈ Sj−1|s>lj}(supuesto que {s∈Sj−1|s>lj} 6=∅) son valores válidos con los que se cumple la propiedad del buen prefijo independientemente del ρ, entonces no existe ningún λ > ljque lo permita. Demostración. Por el corolario 2.4.10, es claro que solo tenemos que probarlo con dos valores candidatos a ρ. La demostración es análoga al lema 2.5.1 teniendo en cuenta además que hay que tener en cuenta la satisfacibilidad del lema 2.4.7. Lema 2.5.3 (Siguiente izquierdo simplificado).Sea vl j= (l0, r0, ..., lj−1, rj−1). Si λ0=lj+ 1 no es un valor válido con el que se cumple la propiedad del buen prefijo independientemente del ρ, entonces no existe ningún λ>ljque lo permita. Demostración. Por el lema 2.5.2, nos basta probar que si λ0=lj+ 1 no es un valor admisible para el vector v0, entonces λ00 = m´ın{s∈Sj−1|s > lj}no lo es tampoco para v0, ya que en caso de que se dé que {s∈Sj−1|s>lj}=∅dicho lema nos garantiza el resultado. Así, razonemos por contradicción: supongamos que existe un ρ≥λ00 tal que v0+λ00 +ρes prefijo de v00. Entonces, como ρ≥λ00 > λ0, es claro que se cumple el lema 2.4.6 para λ00, ρ yv0. Ya que se cumple el lema 2.4.7 para λ, puede suceder que Sj−1=∅, o bien Sj−1={λ00}, o bien λ00 ≤m´ın Sj−1. En el primer caso, es claro que se cumple dicho lema para λ0, y en los otros dos podemos plantear la desigualdad λ0< λ00 ≤m´ın Sj−1; con lo que si λ00 cumple el lema 2.4.7,λ0 también. 34 mínimo de h0 2 0 5 1 5 3 4ies v0=h0 2 1 i(compruébese). Por el corolario 2.4.10 y el teorema 2.4.8, sabemos que cualquier ρdel cual v0+ρsea prefijo cumple que rj= 1. Por ello, v00 tiene de prefijo a v0=h0 2 1 1i. Entonces, dado que h(v00, v0) = 4 = |S0 1|+ 1, estamos en las hipótesis del lema 2.5.8. Los valores obtenidos por el lema 2.5.6 son λ0= 1, ρ0= 2, con lo que estamos en el subcaso 2de dicho lema. Por ello, sabemos que v00 tiene por prefijo v0+λ+σ, donde λ=λ0= 1 yσ= m´ın{s≥ρ0, s ∈S0 j}= m´ın{3,4,5}= 3. En la siguiente etapa del algoritmo sabemos que v0=h0 2 1 1 1 3ies prefijo de v00. Además, h(v00, v0)=2=|Sj|, con lo que estamos en las hipótesis del lema 2.5.9. Así, es claro que v00 =v0+ 4 + 5 ya que h(v00, v0+ 4 + 5) = 0. Ejemplo 2.5.12. Compruébese que el vector v00 del cual es prefijo el vector v0del ejemplo 2.5.5 es v00 =h0 3 1 4 2 5 6 7i(lo cual es inmediato al cumplirse el lema 2.5.9 con v0).  Además, observemos que no hemos hablado de variar los inputs. Es decir, estos lemas suponen que d≥1y en definitiva, como mostraremos, nos permitirá obtener un circuito bien definido sobre un conjunto de k=|E0(C)| ≤ minputs. Sin embargo, no hemos hablado de cómo seleccionar esta cantidad. La respuesta es muy simple: dado un subconjunto Sde {i|0≤i<m}tal que |S|=k, podemos ordenar los elementos de dicho conjunto vía el índice. Los elementos presentes en Sdeterminan unívocamente qué inputs poder elegir y, ya que esto no presenta ningún tipo de complicación técnica, podremos suponer que contamos con un método que nos permite cambiar de inputs sin cambiar la estructura del circuito. Finalmente, notemos que tras obtener v00 mediante este algoritmo, podemos aplicar el corolario 2.3.2 para obtener el mínimo vector gasociado a ˆ C0|dy así definir la clase C0|d∈ Cn,w|d. Además notemos que en todo el proceso realizado no hemos perdido información, esto es, dado C|dpodemos obtener C0|dde manera que todos los niveles no afectados por la teoría mencionada anteriormente no cambian. Por ello, podemos visualizar ˆ C|dcomo una abstracción para simplificar los cálculos de la cual podemos olvidarnos de manera práctica. Recapitulando ideas: hemos conseguido un algoritmo que nos permite, dada una clase ˆ C|d, detectar si hay alguna clase ˆ C0|dsiguiente a ˆ C|dde manera que ˆ C|d+1 =ˆ C0|d+1 (gracias a la propiedad del buen prefijo); y en caso afirmativo, construirla. 2.6. Ampliación del suelo, cambio de nivel y fin del algoritmo Sin embargo, podría suceder que la clase ˆ C0|dque dista 1de ˆ C|d, donde ˆ C|d+1 =ˆ C0|d+1 dentro de ˆ Cn,w|d+1 no cumpliese que |Ed−1(ˆ C0)|=|Ed−1(ˆ C)|. En ese caso, tendría que darse que |Ed−1(ˆ C0)|= |Ed−1(ˆ C)|+ 1 ya que si existe j, d ≤j≤ntal que|Ej(ˆ C)| 6=|Ej(ˆ C0)|, entonces ˆ C|d+1 6=ˆ C0|d+1. Por el lema 2.1.4, el corolario 1.3.3 y la definición de ˆ Cn,w, sabemos que esto solo se puede dar si |Ed−1(ˆ C)|<m´ın{2p, w, δm(d)}. 41 Lema 2.6.1 (Vector mínimo).Dado d≥1y una clase ˆ C|d+1 ∈ˆ Cn,w|d+1 con n > 1tal que p=|Ed(ˆ C)|yk=|Ed−1(ˆ C)|, entonces existe un único vector vd−1(asociado a una única clase ˆ C0|d) de manera que ˆ C0|dsea mínima dentro de ˆ C|d+1. Demostración. Por la definición de bien conectado y la función índice es claro que (0) es prefijo de cualquier vector v. Así, gracias al corolario 2.4.10 existe un ρtal que v0= (0, ρ)es el mínimo prefijo de tamaño 2. En concreto, este vector es prefijo del mínimo vector de vasociado a alguna clase ˆ C|d. Aplicando el algoritmo 2.5.10 podemos extender v0hasta v. La unicidad se da del determinismo del algoritmo. Teorema 2.6.2 (Ampliación del suelo).Existe una clase ˆ C0|dde índice 1más que el de ˆ C|dcon |Ed−1(ˆ C0)|=k+ 1 cumpliendo que ˆ C|d+1 =ˆ C0|d+1 si y solo si k < m´ın{2p, w, δm(d−1)}y el algoritmo 2.5.10 devuelve None para ˆ C|d. Demostración. =⇒Sea ˆ C0|dtal que |Ed(ˆ C0)|=k+ 1. Por el lema 2.1.4 se tiene que k+ 1 ≤2py por el corolario 1.3.3 se da que k+ 1 ≤δm(d−1). Además, por la definición de ˆ Cn,w es claro que k+ 1 ≤w. En definitiva, k+ 1 ≤m´ın{w, δm(d),2p}. Por tanto, k < m´ın{w, δm(d−1),2p}. Finalmente, el algoritmo 2.5.10 debe devolver None ya que el índice entre ˆ C0|dyˆ C|ddista 1y no se cumple que |Ed−1(ˆ C)|=|Ed−1(ˆ C0)|. ⇐=Si el algoritmo 2.5.10 devuelve None para ˆ C|dsignifica que la siguiente clase ˆ C0|d, de existir, cumple que |Ed−1(ˆ C0)|> k. Como k < m´ın{w, δm(d−1),2p}, tomemos k0=k+ 1 y comprobemos que existe una clase ˆ C0|dtal que |Ed−1(ˆ C0)|=k0, ya que si k00 > k0, la clase ˆ C00|d dentro de ˆ C|d+1 tendrá mayor índice. De hecho, nos basta probar que existe una clase ˆ C0|d∈ˆ C|d+1 tal que |Ed−1(ˆ C0)|=k0, ya que por el lema 2.6.1, entonces dicha clase mínima existiría. Así, tomemos v0= (0) y comprobemos que se cumple la propiedad del buen prefijo para algún v00. Tomando ρ= 1, puesto que |S0 −1\{0,1}| = k0−2 = k−1 = |S−1| − 1, entonces |S0 −1\ {0,0}| =|S−1| − 1≤2(p−1) = h(v00, v0+ρ)para cualquier v00 de tamaño 2p. Con lo que se cumple el lema 2.4.5. Por otra parte, ya que ˆ C|des una clase, entonces el vector ˜v0= (0) es prefijo de su vector ˜v asociado y se cumple el lema 2.4.6. Es decir, 2(p−1) = h(˜v, ˜v0+r0)≤2(k2−1−ˆ fn(τ(0, r0))) ≤ 2(k2−1). Comprobemos que dicho lema se cumple también para v0:2(k02−1−ˆ fn(1(0,0))) = 2(k2+ 2k+ 1 −1−0) = 2(k2+ 2) ≥2(k2−1) ≥2(p−1). Por ello, v0cumple el teorema 2.4.8 y en consecuencia existe un vector v00 asociado a ˆ C0|d. Finalmente, nos queda comprobar que dicha clase está en ˆ Cn,w y es fruto de un circuito con minputs, cosa que en el resto de lemas anteriores era algo claro y evidente ya que el número de puertas en la clase ˆ C|dera invariante a las transformaciones realizadas. Para probarlo, probemos en primer lugar que pertenece a ˆ Cn,w|d. Para ello, hay que probar que existe ˆ Den ˆ Cn,w tal que ˆ D|d=ˆ C0|d. Puesto que C∈ Cn,w, entonces existe un valor l, tal que 42 |El(C)|=w, y este no puede ser dpor hipótesis. Así, si existe un l > d tal que |El(C)|=w, entonces |El(C0)|=wy hemos acabado. Si no, necesariamente existe un l < d tal que |El(C)|=w. Probaremos que existe una clase ˆ C|l∈ˆ C|d, con |El(C)|=wy lo haremos de manera constructiva, obteniendo para cada j, l < j < d un vector vjde manera que dichos definan la clase ˆ C|d. Por la proposición 2.1.4 sabemos que si en el nivel jhay kjpuertas, en el nivel j+1 hay al menos η(kj)puertas. Así, definamos kj= m´ax{k+ 1, ηj−l(w)}, l ≤j≤d. Ya que k < k + 1 yCes un circuito se da necesariamente que ηd−l(w)≤k < k + 1, con lo que kd=k+ 1. Además, se cumple que ηl−l(w) = id(w) = w, lo que da que kl=wy de manera obvia obtenemos que kj≤kj−1. Entonces se da la siguiente causística para todo valor j, l < j < d: kj=kj−1=k+ 1. Tomemos en esta situación el vector vj= (0,0,1,1, ..., k, k). Entonces, podemos definir la clase ˆ C0|jcomo ˆ C0|j+1 ∪ {vj}. Además, se cumple que |Ej(ˆ C0|j)|= |Ej(ˆ C0|j+1)|=kjy|Ej−1(ˆ C0|j)|=kj−1=kj. kj=k+ 1, kj−1=ηj−1−l(w)> k + 1. Por la proposición 2.1.4 sabemos que se da la siguiente desigualdad kj< kj−1≤2kj. Así, denotemos p= 2kj−kj−1>0y definamos el vector vj−1= (0,0,1,1..., p −1, p −1, p, p +1, ..., kj−1). Es claro que es un vector de tamaño 2kjy se cumple que aparecen todos los elementos entre 0ykj−1, con lo que la clase ˆ C0|j=ˆ C0|j+1∪{vj} está bien definida y cumple que |Ej(ˆ C0|j)|=|Ej(ˆ C0|j+1)|=kjy|Ej−1(ˆ C0|j)|=kj−1. kj=ηj−l(w)> k + 1, kj−1=ηj−1−l(w). En este caso o bien 2kj=kj−1, con lo que definamos vj= (0,1,2, ..., kj−1)o bien 2kj−1 = kj−1, en cuyo caso definamos vj= (0,0,1,2, ..., kj−1). En ambos casos vjes un vector de tamaño 2kjy podemos definir la clase ˆ C0|jcomo ˆ C0|j+1 ∪{vj}, de manera que |Ej(ˆ C0|j)|=|Ej(ˆ C0|j+1)|=kjy|Ej−1(ˆ C0|j)|=kj−1. En cualquier caso, es claro que podemos obtener la clase ˆ C0|l+1 a partir de ˆ C0|dcumpliendo que |El(ˆ C0)|=wyˆ C0|l+1 ∈ˆ C0|d. Por tanto, ˆ C0|d∈ˆ Cn,w|d. Además, ya que |El(ˆ C0|l+1)|=|El(C)|=w, es claro que w≤δm(l−1). Queda por probar pues que hay un circuito en esa clase generable mediante minputs. Definamos kl=|El(ˆ C0)|(con l=d−1en el caso de que ˆ C0|dtuviese un nivel i>dtal que |Ei(D)|=w); y para todo j, 0≤j < l escribamos kj=σ(kj+1). Así, probemos que si tenemos definido ˆ C0|j+1, podemos definir ˆ C0|jde manera que |Ej−1(ˆ C0|j)|=kj−1ykj−1≤δm(j−1). De hecho, nos encargaremos de dar un vector vjcon el que definir dicha clase. Tomemos v0= (0,0). Por el lema 2.5.6 existen li+1, ri+1 de manera que dado el vector (l0, r0, ...li, ri)se dé que fj(τ(li, ri)) + 1 = fj(τ0(li+1, ri+1)), donde τ= 1 si li=rioi > 0, li−1=li, ri−1=riy0en otro caso y τ0= 1 si li+1 =ri+1 o si li=li+1, ri=ri+1 y0en otro caso. Así, y ya que l0=r0= 0 yfj(1(0,0)) = 0 podemos definir un vector de tamaño 2kjen el que aparezcan todos los términos i, 0≤i<kj−1ya que se da que (kj−1−1)2< kj≤k2 j−1(proposición 2.1.4). Finalmente, ya que k2 j−1≤kj≤δm(j), entonces k2 j−1≤pδm(j) = √m2j=m2j−1=δm(j−1). Repitiendo el argumento un número finito de veces obtenemos que hemos definido una clase ˆ C0|0 de manera que k0≤δm(0) = m. Por tanto, la clase ˆ C0|l+1 pertenece a ˆ Cn,w|ly en consecuencia esto 43 mismo sucede para ˆ C0|d. Sin embargo, podría darse que existiera una clase ˆ C0|dde índice mayor que el de ˆ C|dque no cumpliese que ˆ C|d+1 =ˆ C0|d+1. En ese caso es porque el índice de ˆ C|dinducido en ˆ C|d+1 es máximo; es decir ˆ C|des la última clase de ˆ C|d+1. En este caso, sabemos que dicha clase tiene que cumplir que ˆ C0|d+1 diste 1de ˆ C|d+1 y de manera recursiva podemos aplicar las herramientas que hemos desarrollado en esta sección para obtener una clase ˆ C0|jtal que ˆ C|jdiste 1. Combinando estos dos lemas junto al algoritmo 2.5.10 podremos avanzar dentro de ˆ C|d+1 de manera cómoda y natural, tal y como se puede ver en el ejemplo siguiente. Ejemplo 2.6.3. Sea ˆ C|n−3∈ Cn,w la clase con representación matricial dispersa siguiente (supuesto n > 3, w ≥6yδm(n−4) ≥6):       0 1 0 1 0 2 0 2 1 2 0 5 1 4 2 3             0 1 0 1 0 2 0 2 1 2 0 5 1 4 2 3          0 1 0 1 0 2 − − − −     0 1 0 1 0 2 0 1 2 3   Figura 2.9: Ejemplo de cambio de nivel. Observemos que la clase ˆ C|n−3cumple que |En−4(ˆ C)|= 6 ya que los valores distintos de la última fila son lo que determina dicho valor. En estas condiciones, el algoritmo 2.5.10 devuelve None y el teorema 2.6.2 no se cumple ya que k= m´ın{6, w, δm(n−4)}. Por tanto, nos olvidamos de ˆ C|n−3y pasamos a considerar ˆ C|n−2, de lo que da fe el color grisáceo que toma la fila n−3. En este caso, el algoritmo 2.5.10 vuelve a dar None, pero esta vez sí se cumple el teorema 2.6.2 ya que 3<m´ın{2·2, w, δm(n−3)}= 4. Por tanto sabemos que la nueva clase ˆ C0|n−2cumple que |En−2(C0)|= 2,|En−3(C0)|= 4. Utilizando el lema 2.6.1, podemos fácilmente obtener que vn−3=h0 1 2 3i. Como se ha podido ver, a veces es necesario comprobar de manera sucesiva dicho lema para poder obtener la siguiente clase. Además, en cada subida, perdemos información sobre la estructura del resto de niveles, información que de alguna manera tendremos que recuperar de nuevo. Corolario 2.6.4 (Fin del algoritmo).Si |En−1(ˆ C)|= m´ın{2p, w, δm(n−1)}y no existe ˆ C0|n−1 tal que la diferencia de índices con ˆ C|n−1diste 1, entonces no existe ningún circuito ˆ C0de índice 44 mayor que ˆ Cen ˆ Cn,w. Demostración. Se deduce trivialmente del teorema 2.6.2 con d=n. 2.7. Retorno a los circuitos: representante mínimo y circuito inicial Todos los resultados anteriores nos ayudan a avanzar en Cn,w con la abstracción de las clases. Sin embargo, el objetivo inicial era trabajar con circuitos, no con clases. Así, trataremos de, una vez obtenida una clase, recuperar el mínimo circuito de dicha clase. En primer lugar, notemos que todo circuito Ces equivalente a C|0. Por ello, nos basta con tener un método para descender entre clases de manera que dado C|del representante C|d−1sea mínimo dentro de C|d. De hecho, nos basta con analizarlo desde ˆ Cn,w|dya que podemos aplicar el corolario 2.3.2 entre cada representante ˆ C|dpara obtener la minimalidad (es rutinario comprobarlo utilizando el índice). Lema 2.7.1. Sea Cun circuito de profundidad n > 1y anchura arbitraria y sean d, d0≥0, d > d0, k=|Ed(C)|, k0=|Ed0(C)|tal que ηd−d0(k0)≤kyσd−d0(k)≤k0. Entonces existe una clase ˆ C0∈ˆ Cn|d0que cumple que ˆ C0|d+1 =ˆ C|d+1 y que para todo l, d0≤l≤dse da que |El(ˆ C0)|=kl, donde kl= m´ax{σd−l(k), ηl−d0(k0)}. Además el índice de esta clase (obtenido al comparar clases de Cn|d0dentro de ˆ C|d+1) es mínimo. Demostración. En primer lugar notemos σ(z)≤zyη(z)≤zpara cualquier z≥0y que kd=k yk0 d=k0. Gracias al corolario 2.1.5 sabemos que |El(C)| ≥ σd−l(k). Por otra parte, aplicando la proposición 2.1.4 de manera sucesiva, obtenemos que |El(C)| ≥ ηl−d0(k0). Por ello, |El(C)| ≥ m´ax{σd−l(k), ηl−d0(k0)}. Además, del hecho de que Csea un circuito, es claro que podemos tomar el resto de niveles de C0no mencionados en el lema idénticos a C. Finalmente, gracias de nuevo a la proposición 2.1.4, es claro que una clase que cumpla que |El(ˆ C)|=kly|El−1(ˆ C)|=kl−1está bien definida. El además es claro gracias a la aplicación reiterada del lema 2.6.1 para todo l6= 0 y del de menor subconjunto si l= 0; teniendo en cuenta que todos los resultados mencionados se aplican independientemente de la anchura del circuito (aunque las usemos siempre con restricción). Corolario 2.7.2 (Extensión mínima).Sea Cun circuito en Cn,w y sean d, d0≥0, d > d0,k= |Ed(C)|, k0=|Ed0(C)|tal que ηd−d0(k0)≤kyσd−d0(k)≤k0y para algún nivel d00 de la forma d00 ≥d od00 ≤d0se da que |Ed00 (C)|=w. Entonces existe una clase ˆ C0∈ Cn,w|d0que cumple que ˆ C0|d+1 = ˆ C|d+1 y que para todo l, d0≤l≤d, se da que |El(ˆ C0)|=kl, donde kl= m´ax{σd−l(k), ηl−d0(k0)}. Además el índice de esta clase (obtenido al comparar clases de Cn,w|d0dentro de ˆ C|d+1) es mínimo. 45 Demostración. Por el lema 2.7.1 sabemos que kl≥m´ax{σd−l(k), ηl−d0(k0)}y por la observación realizada en dicho lema, kl≤m´ax{k, k0}. Así, del hecho de que para todo l, d0< l < d, se dé que l6=d00, entonces es claro que la clase ˆ C0|ddefinida en dicho lema está en ˆ Cn,w|d. Teorema 2.7.3 (Representante mínimo).Sea d≥0, y sea una clase ˆ C|d+1 de manera que k= |Ed(ˆ C)|. Entonces existe una clase ˆ C0|0tal que ˆ C0|d+1 =ˆ C0|d+1 de manera el índice de ˆ C0|0sea mínimo. Demostración. En estas condiciones, podemos tener dos situaciones: que exista un nivel l, d ≤l≤n, tal que |El(C)|=wo que no exista dicho nivel. Si existe dicho nivel, entonces nos es igual cuántos inputs tomar o el número de puertas empleadas en cada nivel siempre que el circuito esté bien formado (es decir, cumpla la proposición 2.1.4 y no tenga un nivel con más de wpuertas). Así, dado que σd(k)≤σd(k)y(ηd◦σd)(k)≤k, podemos tomar d0= 0, k0=σd(k)en el corolario 2.7.2 para obtener la mínima clase ˆ C0|0, ya que no hay menor valor de k0posible. Si no, apliquemos el lema 2.1.7 para obtener el mínimo ltal que |Ed(C0)|=wpara cualquier circuito C0. Ya que l < d, podemos aplicar el corolario 2.7.2 con d=l,k=w,d0= 0 yk0=σl(w) para obtener una clase ˆ C00|0tal que ˆ C00|l=ˆ C|l(y en consecuencia ˆ C00|d=ˆ C|d) de manera que el índice de ˆ C00|0sea mínimo dentro de ˆ C|d. Ahora bien, ˆ C00|0se puede extender a un circuito tal y como observamos aquí. Con lo que podemos hablar de C00 o de ˆ C00|0casi indistintamente (nos es igual qué C00 ∈ˆ C00|0tomar para continuar con la demostración). Por tanto, apliquemos de nuevo el corolario 2.7.2 vía C00 con dykdefinidos en las hipótesis y d0=l,k0=w; aprovechando el hecho de que la desigualdad ηd−l(w)≤kse da en el circuito C. Así, obtenemos una clase ˆ C0|ltal que ˆ C000|d=ˆ C00|d=ˆ C|dde índice mínimo sobre ˆ C|d. Así, sea C000 un circuito de ˆ C000|l. Apliquemos de nuevo el mismo corolario con C000,d=l, k =w, d0= 0 yk0=σl(w)para obtener ˆ C0|0de índice mínimo sobre ˆ C000|l=ˆ C|l(y en consecuencia de índice mínimo sobre ˆ C|d). Notemos finalmente que por la demostración del lema 2.7.1, para todo jtal que 0≤j < l, los vectores vjasociados al nivel j-ésimo de ˆ C0|0coinciden con los vectores vjde ˆ C00|0, con lo que computacionalmente solo es necesario aplicar el corolario dos veces. El nombre de este teorema claramente tiene su origen en la posibilidad de partir de una clase de Cn,w|dy transformarla en un circuito en Cn,w con mínimo índice. Algoritmo 2.7.4 (Representante mínimo).Obtención del mínimo representante de C|d 46 Algoritmo 5 Representante mínimo Require: d,C,vp while d > 0do .Subrutina extensión. p←vp[d] k←v[d−1] C←Vector mínimo g←Tipo mínimo C←C∪(v, g) d←d−1 end while return C Require: d,C|d C←C|d if Existe j≥dtal que |Ej(C)|=wthen .Caso 1del Representante mínimo vp←Extensión mínima . vpcontiene a todos los kl. else .Caso 2del Representante mínimo l←Mínimo nivel vp1←Extensión mínima .Aplicado para obtener C00. vp2←Extensión mínima .Aplicado para obtener C000. vp←vp2∪vp1 end if C←Subrutina extensión return C Por las observaciones realizadas en el algoritmo 2.5.10, es claro que el coste de este algoritmo está en O(dp log(p)). Sin embargo, notemos que gracias a nuestro recorrido en dos etapas (tipos y cableado), conseguimos retardar la ejecución de este algoritmo dentro del nivel d. Ejemplo 2.7.5. Veamos de manera práctica la aplicación del algoritmo 2.7.4 a la clase ˆ C|3∈ C4,4 sobre m≥2inputs siguiente: 47 "0 1 0 2 1 2#        0 1 0 2 1 2 − − − − − − − − − − − − − − − −                 0 1 0 2 1 2 0 0 0 1 2 3 − − − − − − − − − −                0 1 0 2 1 2 0 0 0 1 2 3 0 0 0 1 0 1 1 1 − −                 0 1 0 2 1 2 0 0 0 1 2 3 0 0 0 1 0 1 1 1 0 1         Figura 2.10: Ejecución del algoritmo 2.7.4 a partir de ˆ C|3. En primer lugar, observemos que ˆ C|2no tiene ningún nivel con 4puertas. Así, aplicando el lema 2.1.7 obtenemos que l= 2 y por el corolario 2.7.2 obtenemos que k2= 3, k1= 4, k0= 2. Así, el vector mínimo cuando p= 3, k = 6 es h0 0 0 1 2 3i, el vector mínimo cuando p= 6, k = 2 es h0 0 0 1 0 1 1 1iy finalmente, la mínima colección de 2inputs es h0 1i  Ahora, y gracias a todos los lemas desarrollados podemos responder algo fundamental: ¿cuál es la primera clase que debemos tomar? Para ello, demostremos el siguiente teorema de manera constructiva. Teorema 2.1.8. El conjunto Cn,w no es vacío si y solo si dado d=dlog2(m´ax{2,logm(w)})e, se da que ηn−d(w)=1. Demostración. Una de las implicaciones ya la demostramos en su momento, así que es momento de completar la prueba. En primer lugar observemos que existe una correspondencia natural entre los circuitos Cde profundidad ny los circuitos de profundidad n+1 que son de la forma C0:=id(C, C). La idea de esta demostración consiste en tomar un elemento arbitrario de Cny obtener un elemento de Cn,w. Dado que ηn−d(w)=1, obtenemos trivialmente que ηn−d(w)≤1yσn−d(1) = 1 ≤w. Tomemos 48 ˆ C|n+1 = (0,0). Notemos que podemos replicar la demostración de la segunda parte del teorema 2.7.3 para d=n, k = 1 utilizando el lema 2.7.1 (sin garantizar en ningún momento que pertenece el circuito a ˆ Cn,w). Así, analizando la clase obtenida ˆ C|0, observamos que |El(C)|=wy que Ej(C)≤w si j6=l, con lobtenido vía el lema 2.1.7. Solo hemos tenido que cambiar la justificación de por qué ηn−d(w)≤1para de manera constructiva obtener un elemento de ˆ Cn,w. Finalmente, gracias al corolario 2.3.2 podemos obtener un representante C00 ∈C00|n+1. Este elemento está en C|n,w, con lo que hemos acabado la demostración. Además, notemos que el circuito obtenido es el mínimo circuito según el índice y a este circuito lo denominaremos circuito inicial. Como era de esperar, no podemos hablar del caso base de un algoritmo sin conocer su estructura. Por ello es su tardía aparición. Si repasamos con cuidado el ejemplo 2.1.13, es claro que este ejemplo representa el circuito inicial con los valores m= 6, n = 4, w = 3. Además, en este ejemplo se ve bien la necesidad de permutar los inputs, ya que este circuito utiliza solo 2de los 6que tiene a su disposición. Algoritmo 2.7.6 (Circuito inicial).Obtención del circuito inicial. Algoritmo 6 Circuito inicial Require: n, w, m ∈Z, l =dlog2(m´ax{2,logm(w)})e, ηn−l(w)=1 C← ∅ C←Representante mínimo return C Demostración. La corrección de este algoritmo se sigue del teorema 2.1.8. Además, su coste está en O(nw log(w)), más solo se va a llamar una única vez. Ejemplo 2.7.7. Mostraremos, por completitud, un ejemplo de circuito inicial.         0 0 0 1 0 0 1 2 0 0 0 1 0 1 0 1         Figura 2.11: Ejemplo de circuito inicial en C4,3con m≥2inputs.  Escribamos, en aras de resumir este capítulo, el algoritmo entero con el que recorrer Cn,w. Algoritmo 2.7.8 (El algoritmo del índice).Recorrido de Cn,w 49 Algoritmo 7 El algoritmo del índice Require: n, w, m ∈Z, ηn−1(w)=1, m ≥σ(w) C←Circuito inicial L←[C] σ←Mínima permutación. while Cno sea None do .Equivalente a Fin del algoritmo. if Existe σ0> σ then .Podemos cambiar los inputs. C←(C\σ)∪σ σ←σ0 else d←1 while d≤ndo g0←Incremento del tipo v0←Incremento del cableado if gno es None then C|d←(C|d\g)∪g0 g←g0 break else if vno es None then g0←Tipo mínimo C|d←(C|d\(v, g)) ∪(v, g0) (v, g)←(v0, g0) break else if Se cumple el teorema Ampliación del suelo then v0←Vector mínimo g0←Tipo mínimo C|d←(C|d\(v, g)) ∪(v, g0) (v, g)←(v0, g0) break end if .else Tenemos que cambiar de clase C|d+1 d←d+ 1 end while if d=n+ 1 then C←None else C←Representante mínimo end if end if L←L∪[C] end while 50 número de puertas en un nivel repercute de manera más directa en la endogamia del nivel inferior que en el caso anterior. Además, tenemos el siguiente lema: Lema 3.3.9. Sea Cde profundidad n. Si l∈N,0≤l < n, la endogamia entrelazada en el nivel l de Cestá entre 0y1. Demostración. Análoga al lema anterior. En consecuencia y de manera análoga, podemos hablar del siguiente concepto. Definición 3.3.10. Dado un circuito Cde profundidad n, definimos la endogamia multinivel entrelazada como la función vectorial ˆee(C)=(ee0(C), ..., een−1(C)). Ejemplo 3.3.11. Mostremos ahora la endogamia multinivel entrelazada en el ejemplo 3.1.1. En este caso ee0≈0,2187,ee1= 0,1250,ee2≈0,2103 yee3= 0. Por tanto, la endogamia obtenida es ˆee(C) = (0,2187,0,1250,0,2103,0). Esta definición aparentemente proporciona algo más de discriminación, ya que distingue el nivel 3del nivel 1. Con ello, las clases de circuitos obtenidos serán de un mayor espectro y se podrán analizar con mayor detalle. Sin embargo, pudiera ser que esta definición esté excesivamente ligada al circuito y dificulte la clasificación de los mismos según la función que computen, que es el objetivo último de este capítulo. 3.4. Endogamia por colapso Sea Cun circuito de profundidad ny sea ˆeun vector de dimensión ncuyas componentes están normalizadas. Nuestro objetivo en esta y las siguientes secciones será buscar combinaciones lineales de las componentes de ˆede manera que la definición resultante se comporte adecuadamente según nuestros estándares. Definición 3.4.1. Dado v= (v0, ..., vn−1)∈Rndecimos que ves un vector de coeficientes si todas sus componentes son no negativas y n−1 P i=0 vi= 1. Definición 3.4.2. Dado un circuito Cde profundidad n, decimos que una función f∈ C → [0,1] es una endogamia por colapso ponderado si existe un vector de coeficientes vC∈Rntal que f(C) = vC·ˆe(C). Intuitivamente, el apellido por colapso de esta definición se basa en que, al pasar un circuito de su representación maximal a su representación minimal, varias de las puertas han podido acabar resultando la misma, colapsando a un representante. Sin embargo, la ponderación de estos colapsos se deja al consumidor y eso es lo que vamos a tratar de estudiar. Lema 3.4.3. Sea Cun circuito de profundidad ny sea vCun vector de coeficientes asociado a C. Entonces vC·ˆe(C)∈[0,1]. 57 Demostración. Ya que vC= (v0C, ..., vn−1C)cumple que todos sus coeficentes son menores o iguales que 1y dado que ˆeC= (e0(C), ..., en−1(C)) tiene todas sus componentes menores o iguales que 1, tenemos que vC·ˆe=n−1 P i=0 viC·ei(C)≤ n−1 P i=0 viC= 1. Por otra parte, al ser tanto vCcomo ˆe(C)no negativos, se cumple que vC·ˆe(C)≥0. 3.4.1. Endogamia por colapso mínimo y máximo Una primera idea sería suponer que las endogamias por nivel son independientes y que quizás lo más sencillo sea coger el menor o el mayor valor de estos respectivamente. Así, proponemos las siguientes definiciones. Definición 3.4.4. Definimos la endogamia por colapso mínimo como la función ecmin ∈ C → [0,1], definida así: ecmin(C) = m´ın{el(C),0≤l < n}, donde nes la profundidad del circuito C. Definición 3.4.5. Definimos la endogamia por colapso máximo como la función ecmax ∈ C → [0,1], definida así: ecmax(C) = m´ax {el(C),0≤l < n}, donde nes la profundidad del circuito C. Ambas definiciones se pueden ver como un caso particular de una endogamia por colapso ponderado tomando como ponderación al vector vC= (∂1,k, .., ∂n−1,k), donde kes el menor índice tal que la endogamia de Cen dicho nivel es mínima (respectivamente, máxima) y ∂i,k es la delta de Kronecker. Sin embargo, vamos a analizar estas definiciones brevemente para ver si son convenientes. Lema 3.4.6. La endogamia por colapso mínimo de un circuito de profundidad nsolo toma los valores 0ylog2n−2+1(2). Demostración. Sea Cun circuito de profundidad n. En el nivel n−1hay una o dos puertas. Si hubiese dos, entonces la endogamia de dicho nivel sería 0ya que cada circuito de profundidad n−1solo podría aparecer una única vez. Si no, la endogamia de este nivel sería log2n−(n−1+1)+1(2) y podemos proceder de manera inductiva, suponiendo que hemos probado que ∀l, k < l ≤n, en el nivel lhay exactamente una puerta o bien existe un nivel intermedio en el que la endogamia es nula y continuamos razonando como en el nivel n−1. En un número finito de pasos hemos obtenido que o bien en algún nivel se alcanza el valor 0, o ˆe= (1,log32, ..., log2n−2+1(2)). Por tanto, ecmin(C)∈ {0,log2n−2+1(2)}. En definitiva, esta definición no aporta demasiado ya que discrimina de manera muy gruesa la diversidad de circuitos. Sin embargo, no podemos realizar un análisis así sobre la endogamia por colapso máximo, ya que en circuitos no extremos estos valores toman valores arbitrarios, pudiéndose alcanzar tanto la cota mínima, 0, cuando el circuito está en representación maximal hasta la cota máxima, 1, cuando el circuito tiene únicamente npuertas. Por ello, esta última puede ser considerado como una métrica razonable. 58 Ejemplo 3.4.7. Calculemos rápidamente la endogamia por colapso mínimo y por colapso máximo en el ejemplo 3.1.1. En este caso, ecmin(C)=0yecmax(C)=0,4206. Aún así, estas dos definiciones generan dudas en cuanto a si son capaces de recoger toda la expresividad que la definición de circuito tiene. Por ello, vamos a proponer nuevas definiciones de endogamia. 3.4.2. Endogamia por colapso directo Una idea bastante razonable es suponer que no todos los tipos de circuitos influyen de la misma manera. Por ejemplo, si un circuito de profundidad 1es utilizado por un gran número de circuitos de profundidad 2es claro que el cambio de valor en su evaluación puede afectar mucho más en el resultado final. Este puede no se debe tomar como un axioma ni como una variable probabilística, sino como la intuición que guiará esta definición. Además, cuanto más aumentemos la profundidad de los circuitos, un cambio en la evaluación de dicho circuito se propagará a priori a menos circuitos. Por todo ello: Definición 3.4.8. Definimos la endogamia por colapso directo como la función ecd ∈ C → [0,1], definida así: ecd(C) = vd·ˆe(C), donde vd=1 1−2−n(2−1,2−2, ..., 2−n)ynes la profundidad del circuito C. Es claro que vdes un vector de coeficientes ya que la suma de sus componentes es 1. Además, refleja fielmente lo explicado anteriormente. 3.4.3. Endogamia por colapso inverso Sin embargo, podemos realizar un razonamiento inverso al anterior: un cambio en la evaluación de un circuito de profundidades muy elevadas es más probable que se refleje en un cambio real en la evaluación del circuito de manera global. Por ello, quizás nos interese ponderar de manera inversa a lo anterior, focalizándonos en las endogamias superiores y no las inferiores. Definición 3.4.9. Definimos la endogamia por colapso inverso como la función eci ∈ C → [0,1], definida así: ecd(C) = vi·ˆe(C), donde vi=1 1−2−n(2−n,2−(n−1), ..., 2−1)ynes la profundidad del circuito C. Es además inmediato por lo dicho anteriormente que vies un vector de coeficientes. Nótese que en ambos casos se han tomado coeficientes de la forma 2−ksolamente por el hecho de que su representación maximal es un árbol equilibrado donde el número de puertas es siempre potencia de dos; podríamos haber elegido otro vector de coeficientes y haber razonado de manera análoga con estas dos definiciones. Ejemplo 3.4.10. La endogamia por colapso directo asociado al ejemplo 3.1.1 es ecd(C)≈0,3378 y la endogamia por colapso inverso resulta eci(C)≈0,1689. Intuitivamente esto quiere decir que si estimamos que la causa de la endogamia está en los niveles superiores, este circuito no lo es, ya 59 que el primer y el segundo nivel se expanden casi en su totalidad. Sin embargo, si nos fijamos en la endogamia directa, tiene más sentido un “alto” valor ya que hay a la postre pocos nodos.  3.4.4. Endogamia por colapso entrelazada Otra idea que puede ser interesante es tratar de medir la propagación de manera directa e inversa, pero teniendo en cuenta la endogamia entrelazada. Así, podemos realizar un análogo al caso anterior con estas definiciones. Definición 3.4.11. Definimos la endogamia por colapso directo entrelazada como la función ecde :C → [0,1] definida como: ecde(C) = vd·ˆee(C), donde vdes el vector de coeficientes de la definición 3.4.8. Definición 3.4.12. Definimos la endogamia por colapso inverso entrelazada como la función ecie :C → [0,1] definida como: ecie(C) = vi·ˆee(C), donde vies el vector de coeficientes de la definición 3.4.9. Finalmente, trataremos de refinar la idea directa teniendo en cuenta, para cada nivel l, a cuántos circuitos del nivel l+ 1 podría afectar en realidad un cambio en la evaluación del circuito. Definición 3.4.13. Definimos la endogamia por colapso bi-entrelazado como la función ecbe :C → [0,1] definida como: ecbe(C) = vb(C)·ˆee(C), donde vb(C) = 1 n P l=1 |El+1(C)| (|E1(C)|, ..., |En(C)|) Ejemplo 3.4.14. Calculemos pues las endogamias por colapso definidas utilizando las endogamias entrelazadas con el ya recurrente ejemplo 3.1.1. Los valores obtenidos son: ecde(C)≈0,1780, ecie(C)≈0,0873 yecbe(C)≈0,1670. Por una parte, obtener que ecde(C)> ecie(C)es lo esperado al poder realizar la misma argumentación que en el ejemplo anterior. Por otra parte, por la naturaleza del vector vdy la del vb(C), los cuales ponderan el número de circuitos a las que afecta un cambio en un nivel, tiene sentido que se dé que ecde(C)≈ecbe(C). De este ejemplo surge una pregunta interesante: ¿introducir el concepto de entrelazamiento genera ruido generando más clases de circuitos o proporciona distinción sin perder la potencia de la definición de colapso directo? 3.5. Umbral de colapso Una pregunta natural de todas estas definiciones es cómo varía la endogamia por colapso de los circuitos en función de los vectores de coeficientes, o lo que es lo mismo, si existe alguna manera de entender cómo poder discriminar utilizando estas endogamias y cómo afectan estas modificaciones. Definición 3.5.1. Se denomina permutación a cualquier función biyectiva σ∈X→X. 60 Nosotros tomaremos usualmente como X={1, ..., n}. Además, dado un vector v= (v1, ..., vn)en Rny una permutación σ, abusaremos de la notación y hablaremos del vector σ(v)=(vσ(1), ..., vσ(n)). Definición 3.5.2. Sea λ= (λ1, ..., λn). Se denomina λ-umbral mínimo a la función uλ∈ C → [0,1] que minimiza σ(λ)·ˆe(C), con σpermutación. Definición 3.5.3. Sea λ= (λ1, ..., λn). Se denomina λ-umbral máximo a la función Uλ∈ C → [0,1] que maximiza σ(λ)·ˆe(C), con σpermutación. Teorema 3.5.4 (Desigualdad de reordenamiento).Sean x1≤ ··· ≤ xnyy1≤ ··· ≤ yndos colecciones de nvalores ordenados. Entonces x1yn+···+xny1≤x1yσ(1) +···+xnyσ(n)≤x1y1+ ···+xnyn, donde σes una permutación cualquiera. [4] Corolario 3.5.5. Dado λvector de coeficientes de tamaño n, las funciones uλyUλse pueden obtener para cada circuito en tiempo en O(nlog(n)). Demostración. De la desigualdad de reordenamiento obtenemos que nos basta con ordenar el vector λy el vector ˆe(C)y multiplicar dichos vectores ordenados adecuadamente. Y eso es claro que se puede obtener en tiempo O(nlog(n)). Definición 3.5.6. Denominamos λ-umbral de colapso de un circuito al intervalo [uλ(C), Uλ(C)]. De todo lo explicado anteriormente nos damos cuenta de que las endogamias por colapso mínimo y máximo no son sino permutaciones del vector v0= (1,0, ..,0), al igual que lo son las endogamias por colapso directo e indirecto con λ=vd. De hecho, ecmin =uv0yecmax =Uv0. Podemos dar la vuelta a este concepto y ver, fijado un vector de coeficientes, cómo varía la endogamia en función de la endogamia de cada nivel. Por ejemplo, en la endogamia por colapso directo, no es lo mismo que los niveles superiores tengan valores altos de endogamia a que sean los inferiores los de alta endogamia; en el primer caso obtendríamos un valor de endogamia por colapso directo mucho menor que en el segundo. 61 Capítulo 4 Gramáticas y circuitos En este capítulo retomaremos el estudio teórico del espacio de circuitos mediante las funciones booleanas que computan, es decir, analizando ev#(C), en aras de buscar relaciones entre los circuitos y las funciones que computan. Recordemos que uno de los conceptos que queríamos estudiar es la relación entre la repetitividad en el patrón de una función y los circuitos que computan estas funciones. Sin embargo, esta idea puede ser observada de muchas maneras. Por ejemplo, la función 00001111000011110000111100001111 se puede ver como repetir cuatro veces el patrón 00001111 o repetir 01111000 tres veces con prefijo 000 y sufijo 01111. Sin embargo, nuestra visión de la repetitividad estará basada en la bisección reiterada del patrón, buscando una única manera de expresar este fenómeno que simplifique, en general, la expresión del mismo. Para ello, nos valdremos del concepto de gramática libre de contexto, un manera de conseguir funciones booleanas de naturaleza muy distinta a la trabajada hasta ahora con los circuitos, pero que sin embargo no son del todo ajenas la una de la otra. 4.1. Gramáticas libres de contexto Recordemos en primer lugar el concepto de gramática libre de contexto. Definición 4.1.1. Denominamos grámatica libre de contexto a la tupla G= (V,Σ,P, S)donde: Ves el conjunto de variables, Σes el conjunto de terminales, Pes el conjunto de producciones, Ses la variable inicial. La principal aplicación de estas gramáticas viene recogida en el siguiente resultado: 62 Teorema 4.1.2. Todo elemento fde F22nse puede obtener mediante una gramática libre de contexto con Σ = {0,1}y un conjunto de variables y producciones irredundantes, es decir, conjuntos cuyos elementos son distintos dos a dos. Demostración. La demostración de este teorema será constructiva e inductiva. En primer lugar, parece razonable tomar dicho conjunto de terminales ya que los elementos de F2son {0,1}. Además, denotaremos int(f), f ∈F22nal número ˜ f(2), donde ˜ fes el polinomio en Z[x]cuyos coeficientes son f= (f0, . . . , f2n)(de manera que los elementos 0y1de F2se correspondan con el 0y el 1de Z). Sea n= 0. Entonces f= 0 of= 1 y definamos P0,int(f)=V0,int(f)→f. Así, tomemos V={V0,int(f)},P={P0,int(f)}yS=P0,int(f). Es inmediato observar que esta gramática genera f y que satsiface las hipótesis del teorema. Así, razonemos por inducción, supuesto que todo elemento de F2n 2es generable por una gramática como en el enunciado. Dado f∈F2n+1 2,fes una 2n+1-tupla de elementos de F2, con lo que denotaremos por f1= (f2n+1−1, ..., f2n)yf2= (f2n−1, ..., f0), de manera que con f=f1·f2 denotaremos la concatenación de tuplas, no el producto. Por hipótesis de inducción, existen dos gramáticas G1= (V1,Σ,P1, S1)yG2= (V2,Σ,P2, S2)de manera que generan f1yf2respectivamente. Por tanto, definamos Pn+1,int(f)=Vn+1,int(f)→Vn,int(f1)·Vn,int(f2)y observemos que denotando P=P1∪P2∪{Pn+1,int(f)},V=V1∪V2∪{Vn+1,int(f)}yS=Pn+1,int(f), obtenemos que G= (V,Σ,P, S)es una gramática libre de contexto que genera fy se cumple que VyPson irredundantes gracias a la notación aplicada en variables y producciones (junto a la definición de conjunto, que no permite multiplicidad). Ejemplo 4.1.3. Sea n= 3 yf= 00011010. Así, el conjunto de producciones que generan dicha función es: V3,26 →V2,1V2,10 00011010 V2,1→V1,0V1,10001 V2,10 →V1,2V1,21010 V1,0→V0,0V0,000 V1,1→V0,0V0,101 V1,2→V0,1V0,010 V0,0→00V0,1→11 donde en cursiva hemos indicado para cada producción Pn,k qué función de tamaño 2ngenera. Para finalizar la sección, ya que hay una interdependencia entre variables y producciones, remarcaremos que realizaremos un abuso del lenguaje, ya que hablaremos indistintamente de ambos conceptos en aras de hacer más liviana la siguiente sección. 4.2. Operadores no simétricos y el teorema de equivalencia Nuestro objetivo, como buenos matemáticos, consistirá en reducir el estudio de las gramáticas al caso anterior de los circuitos, para aprovechar sus nociones y construcciones. Para ello, observemos 63 que las gramáticas expuestas en el teorema 4.1.2 tiene una apariencia de circuitos. Sin embargo, no es tan sencillo comno se querría. Definición 4.2.1. Diremos que un operador P∈ C × C → C0es no simétrico si no es simétrico para todo C1, C2∈ C, C16=C2. Aunque esta definición parece innecesaria, nos sirve para poner el foco en lo siguiente: Vse puede construir de manera idéntica a Ccon un poco más de esfuerzo. Definición 4.2.2. Denotaremos por Vnal conjunto de variables Vn,k empleables por la gramática definida en el teorema 4.1.2 para generar el elemento f∈F22n, donde k=int(f). Lema 4.2.3. El conjunto Vntiene 22nelementos. Demostración. Es inmediato debido a que Vnestá en biyección con F22n. Definición 4.2.4. Denotaremos por ev#0:V0→F2al operador evaluación: ev#0(V0,k) = k. Definición 4.2.5. Denotaremos por ev#n:Vn→F22nal operador evaluación ev#n(Vn,k) = xn·ev#n−1(Vn−1,k1) + ev#n−1(Vn−1,k2). Además denotaremos por Ev#aEv#={ev#n, n ∈N}. Así, observaremos que podemos definir la siguiente puerta lógica: Definición 4.2.6. Denotaremos por ·∈Vn× Vn→ Vn+1 a la puerta lógica concatenación, de manera que el equivalente de dicha puerta sea eq(·)∈F22n×F22n→F22n+1 definido así: eq(·)(f, g) = eq(·)((f2n−1, . . . , f0),(g2n−1, . . . , g0)) = (f2n−1, . . . , f0, g2n−1, . . . , g0), de manera que se cumple que (ev#n+1 ◦·) (V, V 0) = eq(·)(ev#n(V), ev#n(V0)). Como se puede ver, gracias a la flexibilidad de la definición asociada al operador evaluación, podemos de una manera muy cómoda hablar de la puerta lógica concatenación y en consecuencia ver el espacio de variables Vcomo un espacio de circuitos construidos con el operador ·. Sin embargo, esta construcción difiere de la usual tanto en el número de operadores como en el tipo de puerta, al ser claro que la concatenación no es simétrica. Por ello, un objetivo razonable sería buscar una manera de transformar Ven Cpara poder utilizar todas las herramientas mencionadas anteriormente. En concreto, teniendo en mente el objetivo del experimento, de lograr esta transformación podremos aprovecharnos del algoritmo 2.7.8 para recorrer de manera exhaustiva V. Teorema 4.2.7 (Teorema de equivalencia).Todo elemento de Vestá en correspondencia con uno de Cen representación minimal y bien conectado cuando m= 2. Además, se puede lograr esta biyección compatible con el índice en C. Demostración. En primer lugar, por el lema 4.2.3 y el corolario 1.3.3, es claro que para todo n∈Nse da que |Vn|=|Cn|= 22n<∞, con lo que de una manera cristalina observamos que dicha biyección existe y en consecuencia, el grueso del teorema queda ya probado. Sin embargo, mostraremos cómo, de todas las biyecciones existentes, elegir una biyección φcompatible con el índice. Si n= 0, podemos tomar φ(in0) = V0,0yφ(in1) = V0,1. Así, V0≈ C0y podemos hablar de la función índice f0sobre V0. Apliquemos ahora inducción sobre n, de manera que Vn≈ Cny podamos 64 hablar de fnsobre Vn. En ese caso, dado C0:=P(C1, C2)de profundidad n+ 1, pueden darse tres casos: P=id. En este caso C1=C2y en consecuencia, sus índices coinciden. Así, denotando k= 2nfn(C1) + fn(C2), podemos definir φ(C0) = Vn+1,k. P=∨. En este caso fn(C1)< fn(C2)por la buena conexión de C0. Así, denotando arbitrariamente k= 2nfn(C1) + fn(C2), podemos definir φ(C0) = Vn+1,k. P=∧. En este caso también se da que fn(C1)< fn(C2). Así, denotaremos k= 2nfn(C2) + fn(C1), y definiremos φ(C0) = Vn+1,k. Esta aplicación es claramente biyectiva y respeta el índice en el sentido siguiente: dados V1, V2, V3∈ Vntales que V1≤V2≤V3, V16=V3, se da que V1V2≤V2V1< V1V3< V3V1(donde la primera desigualdad es una igualdad si V1=V2). Esto es importante porque esta desigualdad hace corresponder a Vuna función índice que formalmente se define de manera análoga a la de Cy, lo que es más importante, nos permite recorrer Vcon el algoritmo 2.7.8 de una manera natural: solo hay que interpretar el circuito obtenido como una variable. El teorema 4.2.7 se puede enunciar así: en un espacio Ccon un orden total todo operador no simétrico P:C×C → C0se corresponde con dos operadores simétricos P1, P2:C×C → C0tales que para todo C∈ C, P1(C, C) = P2(C, C). Sin embargo, hemos decidido exponerlo con un enunciado más simplificado para ver su aplicación inmediata, aunque ello implique que se difumine la idea de equivalencia implícita en su apellido. Además, gracias a la biyección construida en dicho teorema, los conceptos de endogamia expuestos en el capítulo 3no solo se pueden aplicar, sino que tiene sentido estudiarlos, ya que estructuralmente es lo mismo un circuito que una producción. Por todo ello surgen varias preguntas que no pudimos realizar en dicho capítulo al no haber hablado de estos conceptos: ¿hay alguna relación entre la endogamia de un circuito que computa una función y la producción que genera dicha función? ¿la gramática de una función determina el mínimo número de puertas de un circuito que compute la misma? 65 Capítulo 5 Resultados y conclusiones Finalizaremos el trabajo recapitulando el experimento realizado, exponiendo los resultados obtenidos y extrayendo alguna conclusión de los mismos. Como ya se mencionó en la introducción, el experimento ha consistido en el recorrido exhaustivo del espacio de circuitos, donde para cada circuito generado se ha obtenido la función que este computa y se actualiza una tabla dispersa en la que anotamos para cada función el menor circuito que la computa. Además, se ha recorrido de igual manera el espacio de las gramáticas asociadas a funciones de 5bits, para finalmente tratar todos los datos obtenidos de manera estadística estudiando distintas correlaciones entre variables aleatorias basadas en los conceptos de endogamia y el número de puertas del circuito / reglas de la gramática. 5.1. Implementación del algoritmo del índice Para poder realizar nuestro experimento, hemos realizado una implementación del algoritmo 2.7.8 en C++ [5]. Por claridad del código, se decidió separar en dos secciones de código diferenciadas la generación de circuitos de la evaluación de los mismos. Así, se representó cada circuito en su representación matricial compacta y el circuito en su representación física, como un árbol de punteros compartidos [6]. La necesidad de contar con ambas definiciones tiene la siguiente motivación: el algoritmo del índice trabaja con matrices, mas la evaluación de un circuito nace con esta expresión. Del paso de una expresión a la otra surge la necesidad de trabajar con la expresión matricial compacta, una expresión intermedia entre ambas representaciones; y para paliar los problemas que surgen de manera inherente a la implementación de un árbol de punteros, se ha utilizado la librería [7] para detectar fugas de memoria. Sin embargo, como se vio en el corolario 1.3.3, el número de circuitos de mbits crece de manera doblemente exponencial con la profundidad; por lo que aun restringiendo wel tiempo de ejecución 66 cercana a dicho valor. Sin embargo, la posible existencia de correlación entre el resto de endogamias es muy difusa, y muy ligada al tipo de circuito involucrado. Nótese que el conjunto de circuitos mínimos con el que se trabaja es de mayor cardinalidad que el resto de los tipos de los circuitos. Por ello, consideramos una muestra suficientemente representativa de la correlación entre endogamias el caso de las gramáticas, ya que la diversidad estructural de circuitos es mayor: los circuitos mínimos tienden a tener baja profundidad y anchura por la propia definición de los mismos, pero sin embargo, las gramáticas son circuitos estructuralmente variados, con un amplio rango de número de puertas empleadas por las mismas. Esta afirmación no se debe interpretar como algo basado en un estudio en profundidad de la densidad de circuitos y su tipo de endogamias en el subconjunto analizado, sino como una razonable e intuitiva aproximación basada en la presunción de distribución equiespaciada de las gramáticas que generan funciones computadas por algún circuito mínimo. Por último, destaca la nula correlación entre endogamias y funciones booleanas, lo cual era algo desgraciadamente esperable. 5.6. Correlación entre las endogamias y número de puertas empleadas Por otra parte, una pregunta razonable es ver cuál de estas endogamias refleja mejor el número de puertas empleadas. Para ello, dada la variable aleatoria Easociada a la endogamia de un circuito y la variable aleatoria Gasociada al número de puertas, estudiaremos si hay una correlación entre EyG(caso Endogamia-Puertas), si la hay entre 1−EyG(caso Endogamia opuesta - Puertas) o si existe dicha correlación entre 1 EyG(caso Endogamia inversa - Puertas). 73 End. representaci´on End. colapso m´aximo End. colapso m´ınimo End. colapso directo End. colapso inverso End. colapso bientrelazado End. colapso entrelazado directo End. colapso entrelazado inverso Endogamia - Puertas Op. endogamia - Puertas Inv. endogamia - Puertas Correlaciones endogamias vs puertas - Circuito m´ınimo −1.00 −0.75 −0.50 −0.25 0.00 0.25 0.50 0.75 1.00 Figura 5.8: Circuitos mínimos. Ampliar End. representaci´on End. colapso m´aximo End. colapso m´ınimo End. colapso directo End. colapso inverso End. colapso bientrelazado End. colapso entrelazado directo End. colapso entrelazado inverso Endogamia - Puertas Op. endogamia - Puertas Inv. endogamia - Puertas Correlaciones endogamias vs puertas - Gram´aticas −1.00 −0.75 −0.50 −0.25 0.00 0.25 0.50 0.75 1.00 Figura 5.9: Gramáticas. Ampliar End. representaci´on End. colapso m´aximo End. colapso m´ınimo End. colapso directo End. colapso inverso End. colapso bientrelazado End. colapso entrelazado directo End. colapso entrelazado inverso Endogamia - Puertas Op. endogamia - Puertas Inv. endogamia - Puertas Correlaciones endogamias vs puertas - Romboides −1.00 −0.75 −0.50 −0.25 0.00 0.25 0.50 0.75 1.00 Figura 5.10: Circuitos con forma romboidal. Ampliar End. representaci´on End. colapso m´aximo End. colapso m´ınimo End. colapso directo End. colapso inverso End. colapso bientrelazado End. colapso entrelazado directo End. colapso entrelazado inverso Endogamia - Puertas Op. endogamia - Puertas Inv. endogamia - Puertas Correlaciones endogamias vs puertas - 4-Romboides −1.00 −0.75 −0.50 −0.25 0.00 0.25 0.50 0.75 1.00 Figura 5.11: Circuitos con forma 4-romboidal. Ampliar En primer lugar, observemos, como era de esperar, que la endogamia por colapso mínimo no ayuda a estudiar los circuitos ya que, en general, es idénticamente nula. Así, omitiendo en lo que sigue dicha métrica, prosigamos el análisis. Como se puede observar, en los circuitos mínimos hay una correlación positiva en el segundo caso (endogamia opuesta vs número de puertas) y una 74 correlación negativa en el primero (endogamia vs número de puertas) independientemente del tipo de endogamia. Esto nos lleva a pensar (en contraposición a lo que sucede con las siguientes gráficas) que dado un conjunto de circuitos, un posible test de validación sobre si estos son mínimos o no sería calcular las correlaciones planteadas y observar si dicho conjunto se comporta como en la gráfica expuesta. Por otra parte, en el caso de las gramáticas obtenemos que la endogamia por colapso entrelazado directo no correlaciona con el número de reglas que esta emplea. Además, la endogamia por colapso directo correlaciona de manera opuesta a como lo hacía en el caso de los circuitos mínimos. En el tercer caso, observamos que los circuitos romboidales también se comportan de manera distinta a los circuitos mínimos: la endogamia por representación, colapso inverso y colapso entrelazado inverso se comportan a la inversa que en el caso mínimo. Y finalmente, el caso 4-romboidal nos hace ver algo todavía más interesante: no nos son útiles las endogamias por colapso máximo, colapso inverso y colapso entrelazado inverso; y de las que nos son útiles, la endogamia por colapso directo y colapso entrelazado directo correlacionan de manera opuesta al caso mínimo. Esto tiene su explicación: los circuitos romboidales se han elegido ad hoc con alta endogamia en sus niveles inferiores y baja endogamia en sus niveles superiores, y los 4-romboidales no tienen endogamia alguna siquiera en los 3niveles superiores, lo que conduce a un comportamiento inútil de las endogamias inversas y un comportamiento anómalo de las endogamias directas. Sin embargo, en esta retahíla de diferencias entre un caso y otro nos damos cuenta de un hecho: la endogamia por colapso bientrelazada siempre se comporta de una manera semejante. Este hecho pone de manifiesto la idea intuitiva que yacía sobre la definición de dicha endogamia: en un circuito, todo depende de las conexiones reales, no del nivel en el que nos encontremos. Por ello, parece razonable afirmar que, de todas las endogamias, la que refleja mejor el número de puertas empleadas es esta. 5.7. Correlación entre distintos datasets Una vez hecho el análisis anterior, tratemos de intentar hallar algún tipo de relación entre las endogamias, los circuitos y las funciones que computan para distintos tipos de circuitos. De nuevo, trataremos de estudiar la correlación entre distintas variables aleatorias. En este caso, y definiendo EyGcomo en el apartado anterior, se ha optado por: 1. Reutilización simple: estudiar la correlación entre las variables X= (1 −E1)·G1,Y= (1 −E2)·G2. 2. Reutilización compleja: estudiar la correlación entre las variables X=G1,Y= (1 −E2)·G2. 3. Cociente: estudiar la correlación entre las variables X=E1·G2,Y=E2·G1. 4. Cociente opuesto: estudiar la correlación entre las variables X= (1−E1)·G2,Y= (1−E2)·G1. Intuitivamente en el primer caso tratamos de comparar el número de puertas empleadas en un tipo de circuitos y su exogamia (el valor 1−E) con el mismo valor en otro tipo de circuitos, de manera que algún tipo de correlación directa nos quiera decir que a mayor número de puertas menor valor de exogamia, y por tanto, menor valor de endogamia. 75 La segunda situación es parecida, pero despreciando el término de exogamia en dicha definición. La motivación de dicha decisión es aplicar dicho análisis a circuitos mínimos, donde la endogamia obtenida será, idealmente, la menor posible. En el tercer caso, tratamos de buscar correlación entre E1 E2yG1 G2. Sin embargo, por cuestiones técnicas de precisión se ha optado por esta transformación aún sin ser equivalente. Es decir, los resultados de este análisis no son directamente extrapolables a la transformación (E1 E2,G1 G2), pero igualmente se ha decidido llevar a cabo. Finalmente, el último análisis se justifica de la misma manera. Recordemos, antes de presentar el análisis, que se ha decidido para los conjuntos de circuitos con forma romboidal y 4-romboidal que se tomará, como representante de la clase de circuitos que computan la misma función, al circuito de menor endogamia. End. representaci´on End. colapso m´aximo End. colapso m´ınimo End. colapso directo End. colapso inverso End. colapso bientrelazado End. colapso entrelazado directo End. colapso entrelazado inverso Reutilizaci´on simple Reutilizaci´on compleja Cociente Op. cociente Correlaciones comparativas - Circuito m´ınimo vs Romboides −1.00 −0.75 −0.50 −0.25 0.00 0.25 0.50 0.75 1.00 Figura 5.12: Circuitos mínimos frente a circuitos con forma romboidal. Ampliar End. representaci´on End. colapso m´aximo End. colapso m´ınimo End. colapso directo End. colapso inverso End. colapso bientrelazado End. colapso entrelazado directo End. colapso entrelazado inverso Reutilizaci´on simple Reutilizaci´on compleja Cociente Op. cociente Correlaciones comparativas - Circuito m´ınimo vs 4-Romboides −1.00 −0.75 −0.50 −0.25 0.00 0.25 0.50 0.75 1.00 Figura 5.13: Circuitos mínimos frente a circuitos con forma 4-romboidal. Ampliar Como se puede ver, en ninguno de los dos casos obtenemos algún tipo de relación entre el número de puertas empleado y su endogamia, lo que nos lleva a pensar que este análisis no nos permite diferenciar dos datasets con circuitos distintos ni ayuda en el estudio de las funciones que estos computan. Finalmente, se decidió realizar el mismo análisis confrontando los circuitos mínimos con la gramática asociada a estos. 76 End. representaci´on End. colapso m´aximo End. colapso m´ınimo End. colapso directo End. colapso inverso End. colapso bientrelazado End. colapso entrelazado directo End. colapso entrelazado inverso Reutilizaci´on simple Reutilizaci´on compleja Cociente Op. cociente Correlaciones comparativas - Circuito m´ınimo vs Gram´aticas −1.00 −0.75 −0.50 −0.25 0.00 0.25 0.50 0.75 1.00 Figura 5.14: Circuitos mínimos frente a gramáticas. Ampliar En este caso parece haber algún tipo de relación en los dos últimos análisis, por lo que parece razonable estudiar comparativamente las gramáticas frente a otros tipos de circuitos. End. representaci´on End. colapso m´aximo End. colapso m´ınimo End. colapso directo End. colapso inverso End. colapso bientrelazado End. colapso entrelazado directo End. colapso entrelazado inverso Reutilizaci´on simple Reutilizaci´on compleja Cociente Op. cociente Correlaciones comparativas - Gram´aticas vs Romboides −1.00 −0.75 −0.50 −0.25 0.00 0.25 0.50 0.75 1.00 Figura 5.15: Gramáticas frente a circuitos con forma romboidal. Ampliar End. representaci´on End. colapso m´aximo End. colapso m´ınimo End. colapso directo End. colapso inverso End. colapso bientrelazado End. colapso entrelazado directo End. colapso entrelazado inverso Reutilizaci´on simple Reutilizaci´on compleja Cociente Op. cociente Correlaciones comparativas - Gram´aticas vs 4-Romboides −1.00 −0.75 −0.50 −0.25 0.00 0.25 0.50 0.75 1.00 Figura 5.16: Gramáticas frente a circuitos con forma 4-romboidal. Ampliar Como se puede observar, uno de los invariantes que se preserva en estas tres últimas gráficas es una correlación inversa entre las variables X, Y en el caso cociente para la endogamia por colapso bientrelazado. Junto con la observación de la sección 5.6, en la cual razonábamos que existía una correlación entre el número de puertas y dicha endogamia, esto parece indicar que hay una correlación existente entre el número de reglas de la gramática y el número de puertas que utiliza un circuito vía la transformación de las variables aleatorias realizadas en este caso. 77 Esta propiedad nos puede servir para poder establecer un posible umbral de minimalidad: en función del número de reglas empleadas por la gramática que compute una función booleana y la endogamia de la misma, podemos establecer unas restricciones necesarias sobre la endogamia por colapso bientrelazada de cualquier circuito que compute dicha función. Entonces, estudiando dicha endogamia en profundidad quizás podamos establecer condiciones necesarias para estimar el mínimo tamaño que debe tener un circuito que compute dicha función. En cualquier caso, el diferente comportamiento que esta comparativa tiene al enfrentar dos circuitos entre sí frente a enfrentar circuitos y sus gramáticas, nos da que pensar que quizás, y solamente diremos quizás, nos hallemos ante un nuevo e interesante camino de investigación. 78 Conclusiones Finalizaremos este trabajo con un breve resumen de todo lo obtenido a lo largo de este documento, y explicaremos una serie de proyectos pendientes que podrían surgir como continuación natural de este experimento. En primer lugar, recordemos que el objetivo de este experimento era recabar evidencia empírica de la endogamia de los circuitos y estudiar la relación de esta endogamia con la función computada por estos. Para ello, hemos desarrollado un formalismo matemático muy flexible para definir los circuitos. Este formalismo nos ha permitido de una manera cómoda cambiar el punto de vista entre circuitos y gramáticas allá donde lo hemos necesitado sin mucho esfuerzo, gracias al teorema de equivalencia. Esto nos conduce a la interesante propiedad de que toda la teoría desarrollada para estudiar las gramáticas se puede adaptar de alguna manera para estudiar los circuitos booleanos. Por otra parte, hemos probado que podemos encontrar representantes únicos de nuestros circuitos y dotar al conjunto de los mismos de un orden total gracias a la representación minimal y a la función índice. Esta función índice nos ha servido para desarrollar y demostrar un complejo pero a la vez simple algoritmo con el que recorrer el espacio de circuitos. Complejo por la laboriosidad del mismo y simple por la sencillez de los argumentos empleados en su demostración, los cuales no requieren de vastos conocimientos ni de matemáticas ni de informática. Sin embargo, la implementación y el desarrollo del mismo han sido particularmente frustrantes por el tiempo invertido en programarlo, testarlo y probar todos los resultados que nos conducen a él; lemas resultantes del estudio bajo prueba y error de las condiciones necesarias para recorrer todos los circuitos. Otro obstáculo encontrado en dicho algoritmo ha residido en la inmensidad del espacio estudiado, el cual computacionalmente era inabarcable para el portatil con el que se ha trabajado. Esta inmensidad se reflejó no sólo a la hora de recorrer el espacio, sino a la hora de procesar los datos que en su recorrido obteníamos: todas las decisiones de restringir el conjunto de datos sobre el que analizar nuestros datos (como en el caso de los circuitos romboidales o los 4-romboidales) han sido por la imposibilidad de procesar tal cantidad de información. A mayores, y para poder utilizar los datos recabados, hemos definido una serie de métricas de endogamia y el concepto de λ-umbral con el objetivo de encontrar algún tipo de relación entre los circuitos y las funciones booleanas. Estos conceptos a priori parecían prometedores ya que condensaban de manera adecuada la estructura de un circuito en un valor numérico. Sin embargo, como se ha visto en el capítulo 5, los resultados han sido un poco infructuosos: en general, entre muchas de las métricas existe una correlación y en múltiples ocasiones esto era lo previsible debido a las si79 militudes inherentes en la definición. Y aquellas correlaciones no previstas, aún siendo interesantes, destacan por su escasez. Además, los distintos análisis planteados no han garantizado ningún tipo de certidumbre, sólo meras sospechas. Por otra parte, se abre de manera insospechada un posible camino de estudio: el estudio de la correlación vía endogamia por colapso bientrelazado entre gramáticas y circuitos; algo que no esperábamos encontrar pero que destaca de manera notable frente al resto de resultados. Por otro lado, si echamos la vista atrás y nos fijamos en el concepto de grafo and-inversor introducido en las primeras páginas de este trabajo, observamos que una implementación de circuito utilizando este patrón nos garantiza una mayor eficiencia. En vez de requerir 2minputs para construir nuestros circuitos, exigimos trabajar con 4puertas de dos inputs y 2puertas de solo un input. Así, el cardinal de Cnes 2n·m2n, el cual, confrontado a los (2m)2ncircuitos generados con nuestra definición, conlleva una mejora de 22n−n∈ O(22n). De hecho, se puede comprobar que tanto la función índice como el algoritmo del índice permanecen prácticamente impasibles a esta decisión: todos los lemas son fácilmente adaptables a esta implementación. De hacerse así, la cantidad de circuitos redundantes obtenidos se reduce drásticamente, con lo que se podrían obtener mayor cantidad de datos con los que validar o refutar las conjeturas propuestas. Por último, destaquemos que aunque parezca infructuoso lo logrado con este experimento, no es así: en el proceso de estudiar este espacio se han obtenido resultados interesantes y se plantean nuevas vías de estudio con fuerte carga matemática e informática que a priori son un poco antiintuitivas. Más aún, se ha visto cómo es el proceso de investigación desde su faceta más directa y más sincera, y eso no se aprende en un libro. 80 Conclusions This chapter will briefly summarize all the results obtained during our experiment, and it will also include a discussion of the suitability of some future developable projects from this work. First of all, let us not forget that the objective of this experiment was to collect empiric evidence about the endogamy of the boolean circuits and studying the relation between the endogamy and the boolean functions they compute. For this purpose, we have developed a mathematical formalism to define our circuits. This formalism has allowed us to exchange circuits and grammars wherever it was needed thanks to the equivalence theorem. That leads us to think that every theory involving grammars can be adapted for studying boolean circuits. Moreover, we have found a unique description of our circuits, their minimal representation. Not only it has been defined a total order on the set of circuits, but also an index function which has enabled us to develop and prove a complex, yet simple, sweeping algorithm of the set of boolean circuits. Nevertheless, the time-expensive implementation of this algorithm has carried some frustration, due to testing and proving its correction. In addition, other obstacle found in our algorithm was the immense space studied, unmanageable for the used laptop. This immensity reflected both on sweeping the circuits’ space and processing all the data collected: every datasets reduction is owed to this reason. Additionally, we have defined some endogamy metrics and the concept of λ-threshold in order to find any kind of relation between boolean circuits and the functions they compute. Beforehand, these definitions seemed promising because they summarized adequately the structure of a circuit in a numeric value. Nevertheless, as we have seen in Chapter 5, the results obtained were a bit fruitless: between many metrics there exists a trivial correlation, and the analysis of the data does not give a clear answer of the endogamy problem. Accidentally we have obtained a new research path: the study of the correlation between grammars and circuits by using the biintertwined collapse endogamy. This is something we did not expect to find, but we are definitely glad to have done so. Furthermore, returning the focus to the and-inverter graph mentioned in the introduction of this work, we realize that an implementation of a circuit using this pattern shows a better efficiency: instead of using 2minputs, we need to use twice different gates as we use now. Doing so, the cardinality of Cis 2nm2ninstead of (2m)2n, so the gain resulting is 22n−n∈ O(22n). In fact, it can be proven that both the index function and the index algorithm remain almost identical after this change in the implementation. In this way it may be possible to obtain more irredundant data to 81 validate or refuse our conjectures. Finally, we want to remark that the great achievement of this project is the path followed in its process. We have opened a path which is likely to be enhanced, a path where mathematics and computer science intertwine. Through the process we have acquired investigation skills ungraspable with only the theoretical content of a book. To end up, we would like to highlight the importance of the results not only for themselves but for the wide knowledge and investigation opportunities that have been brought up. 82 0 1 2 3 4 Id de la funci´on en decimal ×109 0.0 0.2 0.4 0.6 0.8 1.0 Valor de la endogamia Umbral m´aximo-m´ınimo - Gram´aticas 0.5 0.6 0.7 0.8 0.9 1.0 Figura 5.23: λ-umbral máximo-mínimo no entrelazado para gramáticas. Volver 89 0 1 2 3 4 Id de la funci´on en decimal ×109 0.0 0.2 0.4 0.6 0.8 1.0 Valor de la endogamia Umbral directo-inverso - Gram´aticas 0.30 0.35 0.40 0.45 0.50 0.55 0.60 Figura 5.24: λ-umbral directo-inverso no entrelazado para gramáticas. Volver 90 0 1 2 3 4 Id de la funci´on en decimal ×109 0.0 0.2 0.4 0.6 0.8 1.0 Valor de la endogamia Umbral m´aximo-m´ınimo entrelazado - Gram´aticas 0.0 0.2 0.4 0.6 0.8 1.0 Figura 5.25: λ-umbral máximo-mínimo entrelazado para gramáticas. Volver 91 0 1 2 3 4 Id de la funci´on en decimal ×109 0.0 0.2 0.4 0.6 0.8 1.0 Valor de la endogamia Umbral directo-inverso entrelazado - Gram´aticas 0.0 0.1 0.2 0.3 0.4 0.5 0.6 Figura 5.26: λ-umbral directo-inverso entrelazado para gramáticas. Volver 92 0 1 2 3 4 Id de la funci´on en decimal ×109 0.0 0.2 0.4 0.6 0.8 1.0 Valor de la endogamia Umbral m´aximo-m´ınimo - Romboides 0.55 0.56 0.57 0.58 0.59 0.60 0.61 Figura 5.27: λ-umbral máximo-mínimo no entrelazado para romboides. Volver 93 0 1 2 3 4 Id de la funci´on en decimal ×109 0.0 0.2 0.4 0.6 0.8 1.0 Valor de la endogamia Umbral directo-inverso - Romboides 0.32 0.33 0.34 0.35 0.36 0.37 0.38 Figura 5.28: λ-umbral directo-inverso no entrelazado para romboides. Volver 94 0 1 2 3 4 Id de la funci´on en decimal ×109 0.0 0.2 0.4 0.6 0.8 1.0 Valor de la endogamia Umbral m´aximo-m´ınimo entrelazado - Romboides 0.52 0.54 0.56 0.58 0.60 0.62 Figura 5.29: λ-umbral máximo-mínimo entrelazado para romboides. Volver 95 0 1 2 3 4 Id de la funci´on en decimal ×109 0.0 0.2 0.4 0.6 0.8 1.0 Valor de la endogamia Umbral directo-inverso entrelazado - Romboides 0.30 0.32 0.34 0.36 0.38 0.40 0.42 0.44 Figura 5.30: λ-umbral directo-inverso entrelazado para romboides. Volver 96 0 1 2 3 4 Id de la funci´on en decimal ×109 0.0 0.2 0.4 0.6 0.8 1.0 Valor de la endogamia Umbral m´aximo-m´ınimo - 4-romboides 0.44 0.46 0.48 0.50 Figura 5.31: λ-umbral máximo-mínimo no entrelazado para 4-romboides. Volver 97 0 1 2 3 4 Id de la funci´on en decimal ×109 0.0 0.2 0.4 0.6 0.8 1.0 Valor de la endogamia Umbral directo-inverso - 4-romboides 0.322 0.324 0.326 0.328 0.330 0.332 0.334 0.336 0.338 Figura 5.32: λ-umbral directo-inverso no entrelazado para 4-romboides. Volver 98 End. representaci´on End. colapso m´ınimo End. colapso m´aximo End. colapso directo End. colapso inverso End. colapso entrelazado directo End. colapso entrelazado inverso End. colapso bientrelazado Id End. representaci´on End. colapso m´ınimo End. colapso m´aximo End. colapso directo End. colapso inverso End. colapso entrelazado directo End. colapso entrelazado inverso End. colapso bientrelazado Id Todos los circuitos −1.00 −0.75 −0.50 −0.25 0.00 0.25 0.50 0.75 1.00 Figura 5.39: Todos los circuitos utilizados. Volver 105 Anexo IV: Gráficas de la sección 5.6 End. representaci´on End. colapso m´aximo End. colapso m´ınimo End. colapso directo End. colapso inverso End. colapso bientrelazado End. colapso entrelazado directo End. colapso entrelazado inverso Endogamia - Puertas Op. endogamia - Puertas Inv. endogamia - Puertas Correlaciones endogamias vs puertas - Circuito m´ınimo −1.00 −0.75 −0.50 −0.25 0.00 0.25 0.50 0.75 1.00 Figura 5.40: Circuitos mínimos. Volver 106 End. representaci´on End. colapso m´aximo End. colapso m´ınimo End. colapso directo End. colapso inverso End. colapso bientrelazado End. colapso entrelazado directo End. colapso entrelazado inverso Endogamia - Puertas Op. endogamia - Puertas Inv. endogamia - Puertas Correlaciones endogamias vs puertas - Gram´aticas −1.00 −0.75 −0.50 −0.25 0.00 0.25 0.50 0.75 1.00 Figura 5.41: Gramáticas. Volver 107 End. representaci´on End. colapso m´aximo End. colapso m´ınimo End. colapso directo End. colapso inverso End. colapso bientrelazado End. colapso entrelazado directo End. colapso entrelazado inverso Endogamia - Puertas Op. endogamia - Puertas Inv. endogamia - Puertas Correlaciones endogamias vs puertas - Romboides −1.00 −0.75 −0.50 −0.25 0.00 0.25 0.50 0.75 1.00 Figura 5.42: Circuitos con forma romboidal. Volver 108 End. representaci´on End. colapso m´aximo End. colapso m´ınimo End. colapso directo End. colapso inverso End. colapso bientrelazado End. colapso entrelazado directo End. colapso entrelazado inverso Endogamia - Puertas Op. endogamia - Puertas Inv. endogamia - Puertas Correlaciones endogamias vs puertas - 4-Romboides −1.00 −0.75 −0.50 −0.25 0.00 0.25 0.50 0.75 1.00 Figura 5.43: Circuitos con forma 4-romboidal. Volver 109 Anexo V: Gráficas de la sección 5.7 End. representaci´on End. colapso m´aximo End. colapso m´ınimo End. colapso directo End. colapso inverso End. colapso bientrelazado End. colapso entrelazado directo End. colapso entrelazado inverso Reutilizaci´on simple Reutilizaci´on compleja Cociente Op. cociente Correlaciones comparativas - Circuito m´ınimo vs Romboides −1.00 −0.75 −0.50 −0.25 0.00 0.25 0.50 0.75 1.00 Figura 5.44: Circuitos mínimos frente a circuitos con forma romboidal. Volver 110 End. representaci´on End. colapso m´aximo End. colapso m´ınimo End. colapso directo End. colapso inverso End. colapso bientrelazado End. colapso entrelazado directo End. colapso entrelazado inverso Reutilizaci´on simple Reutilizaci´on compleja Cociente Op. cociente Correlaciones comparativas - Circuito m´ınimo vs 4-Romboides −1.00 −0.75 −0.50 −0.25 0.00 0.25 0.50 0.75 1.00 Figura 5.45: Circuitos mínimos frente a circuitos con forma 4-romboidal. Volver 111 End. representaci´on End. colapso m´aximo End. colapso m´ınimo End. colapso directo End. colapso inverso End. colapso bientrelazado End. colapso entrelazado directo End. colapso entrelazado inverso Reutilizaci´on simple Reutilizaci´on compleja Cociente Op. cociente Correlaciones comparativas - Circuito m´ınimo vs Gram´aticas −1.00 −0.75 −0.50 −0.25 0.00 0.25 0.50 0.75 1.00 Figura 5.46: Circuitos mínimos frente a gramáticas. Volver 112 End. representaci´on End. colapso m´aximo End. colapso m´ınimo End. colapso directo End. colapso inverso End. colapso bientrelazado End. colapso entrelazado directo End. colapso entrelazado inverso Reutilizaci´on simple Reutilizaci´on compleja Cociente Op. cociente Correlaciones comparativas - Gram´aticas vs Romboides −1.00 −0.75 −0.50 −0.25 0.00 0.25 0.50 0.75 1.00 Figura 5.47: Gramáticas frente a circuitos con forma 4-romboidal. Volver 113 End. representaci´on End. colapso m´aximo End. colapso m´ınimo End. colapso directo End. colapso inverso End. colapso bientrelazado End. colapso entrelazado directo End. colapso entrelazado inverso Reutilizaci´on simple Reutilizaci´on compleja Cociente Op. cociente Correlaciones comparativas - Gram´aticas vs 4-Romboides −1.00 −0.75 −0.50 −0.25 0.00 0.25 0.50 0.75 1.00 Figura 5.48: Gramáticas frente a circuitos con forma 4-romboidal. Volver 114