Es udio de la endogamia de los ci cui os booleanos
Resea ch in o he endogamy o boolean ci cui s
En ique Román Cal o
DOBLE GRADO EN INGENIERÍA INFORMÁTICA - MATEMÁTICAS
FACULTAD DE INFORMÁTICA
UNIVERSIDAD COMPLUTENSE DE MADRID
T abajo de in de g ado - Cu so 2019/2020
Fecha: 26 de junio de 2020
Di ec o es:
Na ciso Ma í Olie
Ismael Rod íguez Laguna
Índice gene al
Ag adecimien os I
Resumen III
Abs ac IV
In oducción y mo i ación 1
Plan de abajo 4
1. El espacio de ci cui os 5
1.1. De iniciones p e ias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2. Rep esen ación minimal y maximal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3. Di e sidad minimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4. O den lexicog á ico de ci cui os . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2. El algo i mo del índice 22
2.1. Resul ados p elimina es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2. Índice y espacio cocien e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3. Inc emen o del ipo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4. La p opiedad del buen p e ijo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.5. Inc emen o del cableado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.6. Ampliación del suelo, cambio de ni el y in del algo i mo . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.7. Re o no a los ci cui os: ep esen an e mínimo y ci cui o inicial . . . . . . . . . . . . . . . . . . . . . . 45
3. La endogamia de los ci cui os 52
3.1. El p oblema de la endogamia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.2. Endogamia po ep esen ación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.3. Endogamias ec o iales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.4. Endogamia po colapso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.5. Umb al de colapso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4. G amá icas y ci cui os 62
4.1. G amá icas lib es de con ex o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.2. Ope ado es no simé icos y el eo ema de equi alencia . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5. Resul ados y conclusiones 66
5.1. Implemen ación del algo i mo del índice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.2. In o mación analizada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.3. Funciones alcanzadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.4. Análisis del λ-umb al.............................................. 70
5.5. Co elación en e las dis in as mé icas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.6. Co elación en e las endogamias y núme o de pue as empleadas . . . . . . . . . . . . . . . . . . . . . 73
5.7. Co elación en e dis in os da ase s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
Conclusiones 79
Conclusions 81
Anexos 83
Anexo I: G á icas de la sección 5.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
Anexo II: G á icas de la sección 5.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
Anexo III: G á icas de la sección 5.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
Anexo IV: G á icas de la sección 5.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
Anexo V: G á icas de la sección 5.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
Bibliog a ía 115
Ag adecimien os
Ag adece es sencillo, solo debes ingi ese sen imien o, más el sen imien o de ag adecimien o no
es ácil de ingi . Po ello, odo lo que bajo es as líneas se ecoge es un econocimien o explíci o a
aquellas pe sonas sin las que es e abajo no hubiese salido adelan e.
Así, en p ime luga debo ag adece la in ini a paciencia y el me iculoso abajo de mis dos
di ec o es, Na ciso Ma í Olie e Ismael Rod íguez Laguna, que me han ayudado y guiado de una
mane a excelen e en el abajo y han sido unos de enso es a ul anza de es e p oyec o con au én ico
e o po lo que epe i ía es a misma expe iencia jun o a ellos sin duda lo si pudie a ol e a ás.
Uno de sus mayo es log os ha sido el sabe delega a iempo el aseso amien o en e ce os cuando
ha p ocedido. En conc e o, quie o ag adece especialmen e a Rubén Ra ael Rubio Cuélla po su
disposición a ayuda me con aspec os écnicos de C++, Au omake y Linux y a enseña me cómo
hace lo de mane a ápida y elegan e a pa es iguales; así como a Ja ie Rod íguez Laguna po
deja me usa una máquina i ual del Ins i u o de Física Teó ica de la UAM pa a pode ejecu a
los expe imen os ealizados.
Además, quie o ag adece a mis pad es el apoyo mos ado du an e es os años de ca e a, ya que
de no se po ellos, po su apoyo económico y emocional y los alo es que me han ansmi ido no
hubie a sido la pe sona que soy y no es a ía hoy esc ibiendo es as líneas que es ás leyendo.
Po una pa e, sin el apoyo de mis amigos no hab ía podido en ega en iempo y o ma es e
abajo, me hab ía desespe ado en el p oceso. Así, po odas las imágenes no deseadas de man eles y
espague is que habéis is o es os meses: Lucía, Isabel, I án, I ene... g acias. G acias inmensas a mis
compañe os de clase, que pa ie on siendo eso y acaba on siendo mi ida; unos buenos y necesa ios
amigos que os ecomiendo a odos encon a alguna ez en ues a ida. A odos y cada uno de
ellos, g acias. Pe o, sin duda a dudas, debo ag adece le es e abajo a F ancisco Bello Rosado,
g an ma emá ico y g an pe sona que me ha dado g andes alo es y amigos que son alo es. Ma ía,
An onio, Ru h, Vic o ia... sois oso os.
Po o a pa e, debo ambién ag adece a Ca men y Ma ía José que con su dedicación y su
en usiasmo me demos a on que la docencia ambién puede se ocacional y des aca on pa a mí de
mane a sob esalien e como p o eso as en la e apa de educación obliga o ia. Vocación que a o una-
damen e han demos ado la mayo pa e de los p o eso es que en es a uni e sidad me han impa ido
y eso e dade amen e se ag adece. Desg aciadamen e, ambién debo menciona al XXI ENEM ha-
be me consumido odo el iempo lib e que es e abajo me ha dejado, pe o habe me b indado a
su ez la opo unidad de conoce a gen e ma a illosa y muy abajado a. G acias chicos po es e
cong eso que casi hicimos pe o no pudo se .
I
Y po úl imo y más impo an e, quie o ag adece e a i, lec o , po no habe imp imido es e
documen o y lee lo en su o ma o digi al. G acias po no malgas a papel de mane a innecesa ia.
Y sob e odo y más impo an e, g acias po lee lo.
II

Resumen
El obje i o de es e abajo consis ió en desa olla un expe imen o que pe mi a analiza múl iples
ipos de ci cui os booleanos y las unciones que es os compu an, de mane a que podamos analiza
las elaciones en e ambos concep os.
En el p ime capí ulo, se expone una de inición o mal del concep o a chiconocido de ci cui o
booleano, se analiza el c ecimien o doblemen e exponencial del conjun o de ci cui os con mbi s
de en ada y se do a de un o den o al a dicho conjun o. En el segundo capí ulo, se demues an
una se ie de esul ados sob e ec o es con de e minadas p opiedades que nos pe mi en eco e de
mane a e icien e el conjun o de ci cui os booleanos que ienen de e minada p o undidad y anchu a.
Es e algo i mo se ha implemen ado en C++ u ilizando écnicas de p og amación concu en e y
es uc u as de da os adecuadas pa a ga an iza la e iciencia del mismo.
A lo la go del e ce capí ulo se exponen dis in as mé icas pa a medi la endogamia de los
ci cui os booleanos, así como in uiciones que jus i ican es as de iniciones. Además, se inco po a un
b e e cua o capí ulo que e sa sob e un ipo de g amá ica lib e de con ex o pa icula que gene a
unciones booleanas y su co espondencia con los ci cui os booleanos.
Finalmen e, es e abajo concluye con un quin o y úl imo capí ulo en el que se analizan los
esul ados ob enidos en es e expe imen o y se exponen las conclusiones consecuen es.
Palab as cla e:
Complejidad de ci cui os. Ci cui o booleano. Endogamia de un ci cui o. Función booleana. Índice
de un ci cui o. P/poly. P opiedad del buen p e ijo. Clase de complejidad. Algo i mo del índice.
Co elación en e unciones y ci cui os.
III
Abs ac
The aim o his p ojec was o de elop an expe imen ha allow us o analyze di e en kinds o
boolean ci cui s and he unc ions hey compu e o s udy he ela ionship be ween bo h concep s.
In he i s chap e , a o mal de ini ion o boolean ci cui s is in oduced, he double exponen ial
g ow h o he se o ci cui s wi h mbi s o inpu is analyzed and a o al o de in his se is de ined.
Du ing he second chap e , some esul s abou ec o s o some kind a e p o ed, which allow us o
e icien ly sweep he se o boolean ci cui s wi h ixed dep h and wid h. This algo i hm has been
implemen ed in C++ using concu en p og amming and adequa e da a s uc u es o ensu e i s
e iciency.
Du ing he hi d chap e , some me ics o measu e he endogamy o boolean ci cui s a e de ined
and some ideas beyond hese de ini ions a e added. In addi ion, he e is a ou h b ie chap e
whe e he ela ionship be ween a special ype o con ex - ee g amma and i s equi alence wi h ou
boolean ci cui s a e discussed.
To conclude, a inal i h chap e is added o analyse he esul s ob ained in he expe imen and
he conclusions hese esul s led us o.
Keywo ds:
Ci cui complexi y. Boolean ci cui . Endogamy o a ci cui . Boolean unc ion. Index o a ci cui .
P/poly. Good p e ix p ope y. Complexi y class. Index algo i hm. Co ela ion be ween unc ions
and ci cui s.
IV
In oducción y mo i ación
Cuando uno se p egun a pa a qué si e es udia un ci cui o o mado po pue as lógicas, lo
p ime o que se le iene a la cabeza es oda la eo ía de la a qui ec u a de compu ado es que nos
dice que, en esencia, un compu ado es un conjun o de pue as lógicas conec adas en e sí. Así,
el es udio de los mismos puede p opo ciona impo an es mejo as en el endimien o de nues os
compu ado es. Po ejemplo, ese es el caso de los g a os and-in e so ; una mane a de modeliza los
ci cui os lógicos que es ú il en dis in os con ex os elacionados con el ha dwa e como en el expues o
en es e a ículo [1].
Sin emba go, no se á ese el camino que omemos en es e documen o. Imaginemos po un mo-
men o un ci cui o lógico o mado po pue as and, o de dos en adas y no de una en ada en el que
no hay e oalimen ación, es deci , es un ci cui o pu amen e combinacional; el cual es á conec ado
aninpu s. Dicho ci cui o, dependiendo de cuál sea el alo de su en ada, de uel e una salida
bina ia, 0o1. Además, es cla o que hay 2ncombinaciones de alo es dis in os que pueden oma
los ninpu s: cada uno de ellos solo puede oma el alo >o el alo ⊥. Así, podemos ep esen a
una unción booleana con 2nbi s, cada uno de ellos asociado a la e aluación de la unción en cada
uno de las combinaciones de alo es que los inpu s pueden oma . Po o a pa e, es cla o que oda
unción es compu able con un ci cui o booleano: nos bas a pa a cada conjun o de alo es del inpu
que den 1 ealiza el and de los mismos y luego jun a los odos con un o . Pe o... ¿cuán as de es as
unciones son compu adas con un ci cui o que u ilice un núme o de pue as polinómico en n?
Eso ya no es an sencillo de a e igua . Tal y como se exhibe en el lib o Compu a ional Com-
plexi y - A Mode n App oach [2], pa a cada alo de nexis e alguna unción booleana que no es
compu able po ningún ci cui o de amaño 2n
10n. De hecho, la g an mayo ía de dichas unciones
no son compu ables po ningún ci cui o de amaño polinómico, ya que, siendo pel polinomio que
aco a el núme o de pue as del ci cui o, el núme o de ci cui os posibles es á en O(p0(n)p(n)(siendo
p0=kp con kcons an e), mien as que el núme o de unciones posibles es á en O(22n). Así, de
mane a na u al, su ge p egun a se qué unciones no son compu ables con ci cui os con un núme o
de pue as polinómico.
La espues a a es a p egun a es una g an incógni a en el campo de la in o má ica eó ica.
Expongamos b e emen e las implicaciones que dicha espues a end ía sob e el es o de campos de
la in o má ica, y po ex ensión, sob e nues a ida dia ia. Deno amos po Pa la clase de complejidad
o mada po el conjun o de p oblemas de decisión que pueden se esuel os en iempo polinómico
po una máquina de Tu ing de e minis a y deno amos po NP al conjun o de p oblemas de decisión
que pueden se esuel os en iempo polinómico po una máquina de Tu ing no de e minis a. Así,
1
el amoso p oblema P s NP se p egun a si P(NP. Es e p oblema es amoso po su di icul ad
(no en ano es uno de los p oblemas del millón de dóla es [3]) y po la e olución cien í ica que
conlle a ía P=NP.
¿Qué iene que e pues P s NP con los ci cui os booleanos? En p ime luga , no emos que se
de ine la clase de complejidad P/poly como el conjun o de lenguajes compu ables po una amilia
de ci cui os booleanos de amaño polinómico, uno po cada amaño de en ada. Así, un esul ado
conocido [2] es que P(P/P oly. Po an o, cualquie p oblema que no pueda esol e se con una
amilia de ci cui os de amaño polinómicos no pod á es a en P. Es po ello que en ende qué
p oblemas equie en amilias de ci cui os de g an amaño pa a se compu ados ab i ía una nue a
ía pa a abo da dis in os p oblemas abie os en el ámbi o de la complejidad; como el ya mencionado
P s NP.
Sin emba go, nues a me a se á mucho menos ambiciosa, pues nos limi a emos a busca qué
ac o es in luyen en el amaño de los ci cui os que compu an una unción booleana. Pa a ello,
el en oque que hemos omado es el siguien e: en un ci cui o booleano i edundan e, es deci , en
el que exis e un camino en e la pue a de salida y odas las demás pue as, si la anchu a del
mismo es á limi ada, en gene al hab á un ni el en el que las pue as se eu ilizan, es deci , hay
dos pue as que ienen como uno de sus inpu s una misma e ce a pue a. A es a si uación la
denominamos endogámica, ya que hay una ue e dependencia en e las pue as de un ni el y las de
su ni el in e io . Así, pa ece azonable p egun a se si es a eu ilización ei e ada de pue as coa a
la exp esi idad del ci cui o y gene a, en consecuencia, unciones calculadas po o os ci cui os más
pequeños. Haciendo una analogía con el caso del á bol genealógico, la endogamia en un ci cui o
booleano se ía equipa able a la endogamia en una amilia en la que, po ejemplo, los pad es de un
hijo sean he manos, p imos, p imos segundos... Desg aciadamen e, las causas y los e ec os de es as
elaciones nos son desconocidos, po lo que na ega en el ma de la endogamia es un iaje a ciegas
que quizás apo e esul ados in e esan es o quizás encallemos a medio camino.
Po ello, se ha diseñado un expe imen o pa a a a de medi es e enómeno. En p ime luga ,
se gene an de mane a exhaus i a ci cui os con p o undidad y anchu a ijas, inc emen ándose ambas
paula inamen e. Así, compu ando la unción booleana asociada al mismo, podemos gua da en una
abla indexada po la unción compu ada el meno ci cui o compu ado (po ejemplo, meno núme o
de pue as, meno p o undidad...). Aún a pesa de la dispe sión que de dicha abla se espe a, po los
esul ados del lib o Compu a ional Complexi y - A Mode n App oach mencionados an e io men e,
elegi amaños de inpu excesi amen e g andes con ie en en un cuello de bo ella la ep esen ación
de las unciones compu adas. Po ello, se ha op ado po oma 5bi s de inpu , de mane a que el
núme o máximo de unciones ob enibles con es e expe imen o es de 225= 232, que coincide con el
máximo núme o de en e os ep esen ables en la mayo ía de lenguajes de p og amación.
T as la ejecución del mismo, enemos po una pa e in o mación del amaño y es uc u a de un
ci cui o que compu a dicha unción, así como in o mación de aquellas unciones que no apa ezcan
en dicha abla: equie en ci cui os con p o undidad o anchu a mayo es de lo conside ado. Po ello,
la in o mación ob enida del mismo no es baladí: puede se i nos pa a ob ene e idencia empí ica
del enómeno de la endogamia. Es a e idencia a a emos de pone la de elie e median e el análisis
de dis in as a iables alea o ias y la co elación exis en e en e las mismas.
Además, o o enómeno elacionado con las unciones booleanas es el de la epe i i idad de
pa ones en la secuencia de bi s que de inen es a unción. Es e enómeno, más e é eo, consis e en la
exis encia de una elación inde e minada en e la complejidad en el pa ón de una unción booleana
2
Además, hagamos no a lo siguien e: al se las pue as lógicas ope ado es simé icos, las uplas
(P, C1, C2)y(P, C2, C1)se compo an igual an e la e aluación y an e iden idad y no iene mucho
sen ido conside a los dis in os ya que en la idea in ui i a que hay po de ás de ci cui o ísico se
da que son exac amen e iguales. Po ello, y du an e del es o del documen o, abaja emos módulo
sime ía de los ope ado es. Es deci , se habla á indis in amen e del ci cui o C:=P(C1, C2)o de
C:=P(C2, C1)pe o no se di á que C:=P(C1, C2)sea igual que C0:=P(C1, C2).
Lema 1.1.19. Si C1yC2son dos ci cui os idén icos, e #(C1) = e #(C2).
Demos ación. Razonemos po inducción. Si C1yC2son dos ci cui os de p o undidad 0, en onces,
po de inición, son iguales. Luego solo puede sucede que e #(C1) = e #(C2). Supongamos que
pa a cualesquie a dos ci cui os de p o undidad nse cumple el lema y sea C=P(C1, C2),C0=
P0(C0
1, C0
2). Como C≡C0, en onces P=P0y, o bien C1≡C0
1, C2≡C0
2, o bien C1≡C0
2, C2≡C0
1.
Po an o e #(C) = (e #◦P)(C1, C2) = eq(P)(e #(C1), e #(C2)) = eq(P)(e #(C0
1), e #(C0
2)) =
(e #◦P)(C0
1, C0
2) = e #(C0), donde se ha aplicado la hipó esis de inducción jun o a la sime ía de
la pue a pa a ga an iza que eq(P)(e #(C1), e #(C2)) = eq(P)(e #(C0
1), e #(C0
2)).
A pa i de aho a conside emos las pue as lógicas pe enecien es al conjun o P={∧,∨, id}
de inidas así: C:=∧(C1, C2)si C16=C2
C:=∨(C1, C2)si C16=C2
C:=id(C1, C2)si C1=C2
donde C1yC2son dos ci cui os de la misma p o undidad, la igualdad no es ía enomb amien o
y dichas pue as ienen un equi alen e na u al, el and y el o lógico de n a iables y la unción
iden idad espec i amen e.
C1C2
Figu a 1.1: Rep esen ación ísi-
ca del ci cui o C:=∧(C1, C2).
C1C2
Figu a 1.2: Rep esen ación ísi-
ca del ci cui o C:=∨(C1, C2).
C1
Figu a 1.3: Rep esen ación ísi-
ca del ci cui o C:=id(C1, C1).
Pa a pode habla de la e aluación de los ci cui os con las pue as elegidas, necesi amos do a
aCde un m-polinomizado , donde mes el núme o de inpu s. Aunque hay in ini as aplicaciones de
es a na u aleza, mos a emos a con inuación una mane a na u al de hace lo.
Lema 1.1.20. El espacio C iene un m-polinomizado compa ible con la biyección en e polinomios
xiy ci cui os de p o undidad 0, al cual llama emos m-polinomizado usual.
Demos ación. Si Ces un ci cui o de p o undidad 0, es equi alen e a un polinomio xi, con lo que
de mane a na u al asocia emos Ccon xi. Además, a ci cui os idén icos asocia polinomios iguales,
9

lo cual es impo an e. Supongamos pues que enemos el m-polinomizado usual de inido pa a odo
ci cui o de p o undidad nde mane a que ci cui os idén icos engan misma imagen y omemos un
ci cui o C:=P(C1, C2)de p o undidad n+ 1. En onces enemos es posibilidades:
P=id. En es e caso di emos que (C0) = (C1)2, ya que (C1) = (C2).
P=∨. En es e caso de ini emos (C0) = (C1) + (C2).
P=∨. Así, oma emos (C0) = (C1)· (C2).
Finalmen e, es inmedia o comp oba que ci cui os idén icos ienen misma imagen g acias a la con-
mu a i idad del anillo F2[x1, ..., xm].
Co ola io 1.1.21. Todo ci cui o de p o undidad n iene asociado un polinomio de mul ig ado n.
Demos ación. Es inmedia o debido a la cons ucción del m-polinomizado usual.
Lema 1.1.22. Sean C1,C2yC3 es ci cui os de p o undidad n ales que C1≡C2yC16=C2.
En onces (e #◦∧)(C1, C2)=(e #◦∨)(C1, C2)=(e #◦id)(C1, C1)y(e #◦P)(C1, C3)=(e #◦
P)(C2, C3), donde Pes una pue a lógica.
Demos ación. Si C1≡C2en onces se da que e #(C1) = e #(C2)po el lema 1.1.19. Así, u ilizando
las p opiedades del equi alen e, es cla o que eq(∧)(e #(C1), e #(C2)) = eq(id)(e #(C1), e #(C1)) =
eq(∨)(e #(C1), e #(C2)); ya que el o y el and lógicos aplicados a la misma upla se compo -
an como la iden idad. De es e modo, la p ime a pa e del lema queda p obada. Finalmen e, es
inmedia o conclui la úl ima pa e pues o que (e #◦P)(C1, C3) = eq(P)(e #(C1), e #(C3)) =
eq(P)(e #(C2), e #(C3)) = (e #◦P)(C1, C3).
Es e lema jun o al 1.1.19 nos hace e que los ci cui os idén icos, aun no siendo iguales, son
in e cambiables g acias siemp e a los equi alen es na u ales que hemos elegido. Es o p opicia á más
adelan e que a emos de e i a epe iciones den o de las ecuaciones de un ci cui o, las cuales se án
gene adas debido a la p esencia de dichos ci cui os idén icos.
Po o a pa e, al lec o a ezado no se le hab á escapado la ausencia en es a elección de pue as
lógicas negado as. Es o se debe al siguien e esul ado:
Teo ema 1.1.23. Todo ci cui o lógico gene ado po las pue as ∧,∨, id y¬ iene un ci cui o lógico
equi alen e donde odos los ¬se encuen en en el ni el de p o undidad 0.
Demos ación. En p ime luga , obse emos que odos los ¬se pueden e como un añadido a las
pue as ∧,∨eid, es deci , ¬◦∧,¬◦∨y¬◦ id. Así, dado un ci cui o a bi a io, podemos conside a
que los ¬solo siguen a una pue a lógica de la mane a explicada.
10
Razonemos una ez más po inducción. Si el ci cui o lógico iene p o undidad 0, es inmedia o.
Así, supongámoslo cie o pa a el ni el ny omemos un ci cui o de p o undidad n+ 1 de inido así:
C0:=P(C1, C2). Si P∈ {∧,∨, id}, ya hab íamos acabado.
Po ello, supongamos que P∈ {¬◦∧,¬◦∨,¬◦ id}. En ese caso, podemos de ini un ci cui o
C0:=P0(¬(C1),¬(C2)), donde P0=Qsi P=¬◦ Q; el cual es equi alen e a C. Po hipó esis de
inducción, exis e un ci cui o C00 equi alen e a C0donde odos los ¬es án en el ni el 0. Po an o,
al se Cequi alen e a C0, queda acabada la p ueba.
La u ilidad de es e eo ema adica en lo siguien e: dado un ci cui o a bi a io Ccon kinpu s
gene ado po ∧,∨, id, lo podemos ep esen a como un ci cui o con m= 2kinpu s, donde los
p ime os kinpu s los iden i ica emos con (x0, ..., xk−1)y los ksiguien es con (1 −x0, ..., 1−xk−1)
(equi alen es a ¬(xi)). Po ello, podemos ol ida nos de las pue as ¬y supone de aho a en adelan e
que el amaño del inpu iene dado po m= 2k. Sin emba go, los esul ados que se expond án no
lo end án en cuen a, es deci , solo in lui án es as elaciones a la ho a de e alua el ci cui o, no de
cons ui lo.
1.2. Rep esen ación minimal y maximal
En es a sección mos a emos cómo ans o ma un ci cui o Cen o o C0de misma p o undidad
apoyándonos en la exis encia de ci cui os idén icos.
Algo i mo 1.2.1 (T ans o mación minimal).Dado un ci cui o Cde p o undidad nde uel e un
ci cui o C0de la misma p o undidad que no iene dos subci cui os idén icos. Además, C0es único
sal o enomb amien o.
Demos ación. La idea de es e algo i mo se á i cons uyendo una colección de ci cui os Ci,0≤
i < n iden i icando ci cui os idén icos, y es o lo ha emos po inducción cambiando el mapa i+1
en cada paso si uese necesa io. Todo ci cui o Cno iene ci cui os de p o undidad 0idén icos po
cons ucción, con lo que omemos C0=C. Así, supongamos que enemos de inido Ck−1y que en
E(Ck−1)no hay dos ci cui os de p o undidad j, 0≤j≤k−1idén icos.
Cons uyamos pues un ci cui o Cksin ci cui os idén icos de p o undidad j, 0≤j≤k < n.
Si no iene dos subci cui os de p o undidad kidén icos, hemos acabado y Ck+1 =Ck. En caso
con a io, sean D, D0@kCk−1de mane a que D≡D0. En onces, pa a odo ci cui o de la o ma
E:=P0(D0,ˆ
D0), con D06≡ ˆ
D0, D0≡D ede inamos k+1(E) = (P0, D, ˆ
D0). Po o a pa e, pa a
odo ci cui o E:=P0(D0ˆ
D0)con D0≡ˆ
D0≡D, ede inamos k+1(E) = (id, D, D). Finalmen e
deno emos po C0
kal ci cui o de p o undidad ncon e ique a Cde inido con el nue o mapa.
El ci cui o C0
k−1ob enido con es a nue a colección de mapas cumple que iene un ci cui o de
p o undidad kmenos y po an o, menos pa es de ci cui os de p o undidad kidén icos en e sí. Si
es e p oceso lo epe imos pa a odos los ci cui os de p o undidad kde mane a i e ada ob enemos
11
un mapa modi icado, k+1, de mane a que en el ci cui o esul an e no hay subci cui os idén icos de
p o undidad k. Así, enemos pe ec amen e de inido Cky en consecuencia, po inducción, Cn=C0.
Finalmen e el además es inmedia o a la is a de la demos ación: o a elección del ci cui o Da
la ho a de modi ica el mapa knos conduce a un ci cui o C00 que es un enomb amien o de C0.
De inición 1.2.2. Di emos que un ci cui o Ces á en su ep esen ación minimal si es idén ico al
ci cui o C0ob enido al aplica el algo i mo 1.2.1 al ci cui o C.
In ui i amen e, la ep esen ación minimal de un ci cui o consis e en exp esa dicho ci cui o con
el meno núme o de pue as man eniendo la misma es uc u a, eliminando pue as epe idas. Sin
emba go, des aquemos que es o no signi ica que el ci cui o que compu a (C)sea mínimo, donde
es el ope ado m-polinomizado usual. A mayo es, des aquemos que es a ep esen ación minimal
es única ya que el algo i mo an e io es de e minis a.
Co ola io 1.2.3. Pa a odo ci cui o Cy su ep esen ación minimal C0se da que e #(C) =
e #(C0).
Demos ación. Es inmedia o siguiendo la demos ación del algo i mo 1.2.1 y aplicando sucesi a-
men e los lemas 1.1.19 y1.1.22.
Sin emba go, no es cie o que un ci cui o y la ep esen ación minimal de dicho ci cui o sean
idén icos, como se puede e en el siguien e ejemplo.
Ejemplo 1.2.4. Sean los ci cui os CyC0dados po las siguien es 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 cla o que C0es la ep esen ación minimal de Cpe o C6≡ C0ya que C:=∧(D1, D2),C0:=
id(D0, D0)y∧ 6=id. In ui i amen e es o es azonable ya que no es lo mismo c ea un ci cui o
usando dos pue as lógicas que usando es.
Pe o sin emba go, es cla o que son esencialmen e el mismo ci cui o eliminando pue as edun-
dan es, po lo que amplia emos la de inición de ci cui os idén icos diciendo que dos ci cui os son
idén icos si sus ep esen aciones minimales son idén icas.
Algo i mo 1.2.5 (T ans o mación maximal).Dado un ci cui o Cde p o undidad nde uel e un
ci cui o C0de la misma p o undidad con 2n−1pue as.
Demos ación. La idea de es e algo i mo se á i cons uyendo una colección de ci cui os Ci, p ≤i≤
2n−1, con p=|E(C)|, de mane a que se di idan duplicidades pa a que lo ezcan ci cui os idén icos
y en cada paso apa ezca una nue a pue a más; y es o lo ha emos po inducción cambiando quizás
12
algún mapa de e ique as en cada paso si uese necesa io. Dado que p=|E(C)|, omemos Cp=C.
Así, supongamos que enemos de inido Ck−1, p ≤k−1< n y que |E(Ck−1)|=k−1y gene emos
Ck.
Si k−1< n implica que hay al menos una e ique a Du ilizada dos eces asociada a un ci cui o de
p o undidad l > 0. Sea además D0una e ique a no u ilizada po ningún subci cui o de p o undidad
lde C. Así, si exis e un ci cui o de p o undidad l+ 1 de inido como E:=id(D, D), y ampliemos
la de inición de ldiciendo l(D0) = l(D)y modi iquemos la de inición de l+1(E) = (P, D, D0),
donde P∈ {∧,∨} y es a pue a se elige de mane a a bi a ia. Si no, es po que exis en dos ci cui os
E, E0 l+1 Cde inidos así: E:=P(D, C1), E0:=P0(D, C2), donde necesa iamen e P, P0∈ {∧,∨}.
En es e caso de inamos l(D0) = l(D)y modi iquemos las de iniciones de E, E0así: l+1(E) =
(P, D, C1), l+1(E0)=(P0, D0, C2).
En cualquie a de los dos casos el núme o de pue as ha aumen ado en 1, con lo que podemos
deno a po Ckal ci cui o de p o undidad ncon e ique a Cde inido con el nue o mapa. En es e
caso se da que |E(Ck)|=k, con lo que en un núme o ini o de pasos hemos acabado.
De inición 1.2.6. Di emos que un ci cui o Cde p o undidad nes á en una ep esen ación maximal
si es idén ico a alguno de los ci cui os C0posibles que se pueden ob ene a pa i de Ccon el
algo i mo 1.2.5.
Co ola io 1.2.7. La ep esen ación maximal de un ci cui o puede no se única.
Demos ación. Se sigue del hecho de que en el algo i mo 1.2.5 si exis e un ci cui o de la o ma
E:=id(D, D)lo podemos sus i ui po E:=∧(D, D0)o po E:=∨(D, D0)de mane a indis in a y
los ci cui os ob enidos son dis in os (y no idén icos).
Co ola io 1.2.8. Si la ep esen ación minimal de un ci cui o Cde p o undidad n iene 2n−1
pue as, la ep esen ación maximal es única y coincide con la ep esen ación minimal.
Demos ación. En p ime luga , po el lema 1.1.16 odo ci cui o iene a lo sumo 2n−1. En onces,
dado que la ep esen ación minimal es única y iene 2n−1pue as, el algo i mo 1.2.5 de uel e un
ci cui o idén ico a C.
Co ola io 1.2.9. La ep esen ación maximal de un ci cui o Cpuede se única y no coincidi con
su ep esen ación minimal.
Demos ación. Sea el ci cui o Cde inido po 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 cla o que no es á en ep esen ación maximal ya que |E(C)|= 6 6=7=23−1. Es o se debe a
que la e ique a E2se u iliza dos eces en las de iniciones. Sin emba go, su ep esen ación maximal
es única ya que solo hay una mane a de de ini una e ique a E3y modi ica la de inición de 2(D1),
a sabe :
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 pa i de es a sección abaja emos con ci cui os en ep esen ación minimal, en los cuales se
cumple que los é minos iden idad e igualdad son equi alen es. Todos los esul ados los expond emos
módulo iden idad de ci cui os, es deci , dos ci cui os con la misma ep esen ación se conside a án
el mismo. Además, los símbolos CnyCse emplea án pa a el conjun o de ci cui os en ep esen ación
minimal de p o undidad ny el conjun o de ci cui os en ep esen ación minimal de p o undidad
a bi a ia espec i amen e.
1.3. Di e sidad minimal
Analiza emos aho a la di e sidad de ci cui os de p o undidad nque se pueden gene a a pa i
de dos de p o undidad n−1.
De inición 1.3.1. Deno amos po δm∈N→Na la unción di e sidad de inida po :
δm(n) = m2n(1.6)
Lema 1.3.2. Si el núme o de ci cui os de p o undidad nes k, en onces el núme o de ci cui os de
p o undidad n+ 1 es k2.
Demos ación. Como el ope ado ∧solo se aplica sob e ci cui os dis in os de Cny en Cnhay k
ci cui os, en onces el núme o de e nas (∧, C1, C2), con C16=C2es k
2=1
2k·(k−1) (donde el
ac o 1
2apa ece po la sime ía del ope ado ). De mane a análoga, el núme o de e nas (∨, C1, C2)
es 1
2k·(k−1). Po úl imo, como el ope ado iden idad se aplica solo a ci cui os idén icos, y hay k
ci cui os en Cn, ob enemos que en Cn+1 hay 2·1
2k·(k−1) + k=k2.
Co ola io 1.3.3. El núme o de ci cui os de p o undidad ngene ables a pa i de minpu s es
δm(n).
Demos ación. Si n= 0, los únicos ci cui os que se pueden gene a son odos aquellos que es án en
Im, y |Im|=m=δm(0).
Supongamos aho a que hemos p obado el co ola io pa a n, es deci , hay δm(n)ci cui os en Cn.
En onces po el lema 1.3.2 en Cn+1 hay δ2
m(n) = δm(n+ 1) ci cui os.
14

Como se puede e , el núme o de ci cui os c ece de mane a doblemen e exponencial con la
p o undidad. Es e esul ado es impo an e ya que nos dice que es e espacio es inaba cable de mane a
p ác ica, solo pa a m= 1 es compu able dicho espacio (el cual es i ial). Además, es o jus i ica el
po qué a la ho a de azona sob e complejidad de p oblemas en el que in e engan ci cui os se exija
que la p o undidad pde dichos ci cui os enga dada po una unción loga í mica (p∈ O(log(n))),
de mane a que |Cp|=δm(log(n)) = mn. De es a mane a, es a íamos abajando sob e un espacio
de amaño exponencial, no doblemen e exponencial, lo que puede ali ia la di icul ad del p oblema
con el que es emos abajando.
1.4. O den lexicog á ico de ci cui os
Finaliza emos es e capí ulo mencionando un o den o al que podemos induci en el espacio de
ci cui os C. Es e o den ob enido se á la guía del algo i mo p esen ado en el capí ulo 2, el cual se
enca ga á de eco e Cap o echando dis in as p opiedades de es e o den lexicog á ico.
En p ime luga , es ablezcamos un o den en el conjun o de inpu s, es o es, digamos a pa i de
aho a que x0< ... < xm−1. Así, hemos do ado de un o den a los ci cui os de p o undidad 0. Veamos
que, solo del hecho de es ablece un o den en e las pue as lógicas, se do a de mane a na u al de
un o den a es e conjun o.
De inición 1.4.1. Dado un ci cui o Cde p o undidad ny una unción :Cn→Z|Cn|, denominamos
índice de C ía al alo (C). A dicha unción la denomina emos unción índice y la deno a emos
po n, donde nes la p o undidad del ci cui o sob e el que se aplica.
De inición 1.4.2. Dadas dos pue as lógicas P, P0decimos que Pes meno que P0si se da que
pa a cualesquie a ci cui os C1,C2de p o undidad n,P(C1, C2)< P0(C1, C2). Así, dado un conjun o
de pue as lógicas di emos que es án o denadas si dadas dos pue as P,P0o bien P < P0o bien
P0< P.
En nues o caso podemos es ablece que ∨<∧, pe o no podemos compa a ninguna de ellas
con la iden idad. En cualquie caso, ya que podemos e id como una ex ensión de ∧, abusa emos
de es e concep o y di emos que exis e un o den en e las pue as, eso es, que ∨<∧ ≡ id. Es a
decisión a bi a ia, ya que podíamos habe is o id como una ex ensión del ope ado ∨, no end á
a pos e io i mucha in luencia; simplemen e se oma po el me o hecho de que queda ex año habla
de ó denes o ales inducidos po conjun os no compa ables. Además, como se e á más adelan e,
solo usa emos es e o den pa a desempa a en e ci cui os dis in os compues os con los mismos
a gumen os (po lo que la decisión omada sob e id no end á peso alguno).
De mane a na u al, es cla o que cualquie unción índice induce un o den sob e Cncon el o den
na u al de Zδm(n). A es e o den inducido lo denomina emos o den en el ni el n. Sin emba go, es as
unciones no solo inducen un o den sob e Cnsino que ambién sob e Cn+1.
Lema 1.4.3. Toda unción índice ninduce un o den sob e Cn+1.
Demos ación. Sea nuna unción índice y sean C:=P(C1, C2),C0:=P0(C0
1, C0
2)dos ci cui os de
p o undidad n+ 1 dis in os. En onces di emos que Ces meno que C0 ía nsi n(C1)< n(C0
1),
15
o bien n(C1) = n(C0
1)y n(C2)< n(C0
2), o bien n(C1) = n(C0
1), n(C2) = n(C0
2), P =∨y
P0=∧. Es e o den es o al en Cnya que es amos abajando sob e ci cui os en ep esen ación
minimal y po an o iden idad es sinónimo de igualdad.
Sin emba go, es e o den no dice nada sob e los ci cui os de p o undidad meno que n; y en
consecuencia, no o dena in e namen e sus subci cui os. Una idea naï pa a ex ende es a de inición
pod ía se in en a ealiza un pequeño apaño al lema an e io en di ección con a ia. Sin emba go,
hace lo así hace que al oma dos ci cui os de p o undidad n > 2, el o den de los subci cui os de
p o undidad n−2no es á uní ocamen e de e minado, es o es, puede da se que C6=C0,En−2(C) =
En−2(C0)y el o den inducido sob e es e subconjun o de ci cui os de Cn−2sea dis in o. Veámoslo
con un ejemplo.
Ejemplo 1.4.4. Sean los ci cui os CyC0de p o undidad n > 2que ienen dados po 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
Figu a 1.4: Rep esen ación ísica del ci cui o C.
C0
C0
1C0
2
D0
1D0
2D0
3
E1E2E3
Figu a 1.5: Rep esen ación ísica del ci cui o C0.
donde se han omi ido de E(C)yE(C0)las de iniciones de E1, E2yE3y odos sus subci cui os. En
es as condiciones es cla o que D1=D0
1, D2=D0
3yD3=D0
2. Y po an o es ácil e que el o den
inducido de mane a ecu si a ía un conjun o de unciones índices que cumplen que D1< D2< D3
(y en consecuencia D0
1< D0
2< D0
3) sob e CyC0lle a ía a que E1< E3< E2en el p ime caso y
que E1< E2< E3en el segundo.
16
Sin emba go, se ía ecomendable busca unas unciones índices úni ocamen e de e minadas pa a
odos los ni eles, de mane a que dichas unciones in e accionen en e sí.
Teo ema 1.4.5. Pa a odo n∈Zexis e una unción índice de e minada uní ocamen e po el o den
en e ci cui os y el o den en e pue as.
Demos ación. En p ime luga , analicemos los ci cui os de p o undidad 0. Así, sea C:=inidonde
0≤i<mde dicha p o undidad y de inamos 0(C) = i. Po an o, 0es una unción índice basada
en el o den en e ci cui os.
Supongamos que exis e aho a nen dichas condiciones, a emos de de ini n+1. Así, dado
C:=P(C1, C2), de inamos n+1(C) = δ2
m(n)−(δm(n)− n(C1))2+ 2( n(C2)− n(C1)) −g(P),
donde g(P)=1si P=∨y0en o o caso. La idea in ui i a de es a unción se encuen a ilus ada
en la igu a 1.6. Veamos pues que n+1 es biyec i a iendo que es sob eyec i a, ya que |Cn+1|=
δm(n+ 1) <∞.
En p ime luga , no emos que n+1(∨(C1, C2)) + 1 = n+1(∧(C1, C2)) y que si n(C1) = 0,
en onces P=id y n+1(id(C1, C1)=0. Así, nues o obje i o se á cons ui una cadena de ci cui os
de p o undidad n+ 1 ales que la di e encia de su e aluación ía n+1 dis e 1y de longi ud δm(n+
1). Es cla o que p obado es o, la sup ayec i idad queda p obada, y po ende, la biyec i idad.
Supongamos que enemos el ci cui o C:=P(C1, C2)y n+1(C) = k. Si P=∨, en onces ∧(C1, C2)
se á el siguien e ci cui o de es a sucesión. Po an o, solo queda analiza los ci cui os de la o ma
C:=P(C1, C2), con P∈ {id, ∧}.
Si n(C2)< δm(n)−1, en onces sea C0
2el ci cui o de p o undidad nque cumple que n(C0
2) =
n(C2) + 1. Así, es ácil comp oba que n+1(P(C1, C2)) + 1 = n+1(∨(C1, C0
2)). En caso con a io,
n(C2) = δm(n)+1, ya que |Cn|=δm(n)y nes á bien de inida. Así, sea C0
1el ci cui o de
p o undidad nque cumple que n(C0
1) = n(C1)+1. En onces n+1(id(C0
1, C0
1)) = n+1(C1, C2)+1.
Finalmen e, con emos el núme o de ci cui os que in e ienen. Po el p ocedimien o empleado,
es cla o que es esul an e de combina el ci cui o de índice n(C)con odos los ci cui os con índice
mayo o igual que es e. Po an o, el ca dinal de es e conjun o 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 de ini i a, g acias a que es a cadena iene longi ud δm(n+1), el índice de su ci cui o minimal
es 0y la dis ancia en e dos elemen os consecu i os es 1, es cla o que n+1 es sob eyec i a.
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
Figu a 1.6: Visualización de la de inición de índice 1cuando m= 3. Los núme os ep esen an los
alo es de 0(C), C ∈ C|0y las lechas indican cuál es el siguien e ci cui o gene ado.
Co ola io 1.4.6. Dado k∈Zy una unción índice ˆ
nsob e un subconjun o de S⊂ Cnde amaño
kexis e una unción índice ˆ
n+1 sob e el conjun o T⊂ Cn+1 gene able po Scompa ible con n.
Demos ación. Po el lema 1.3.2, en Thay k2. Así, sus i uyendo Cn,Cn+1 yδm(n)po S, T yk
espec i amen e en la demos ación del eo ema 1.4.5 ob enemos la unción ˆ
n+1(C) = k2−(k−
ˆ
n(C1))2+ 2( ˆ
n(C2)−ˆ
n(C1)) −g(P), la cual es índice en T. Finalmen e, es inmedia o e que si
C < C0 ía ˆ
n+1 en onces C < C0 ía n+1.
Así, deno a emos a pa i de aho a po Fn={ 0, ..., n}al conjun o o mado po las p ime as
n unciones índice calculadas en el eo ema 1.4.5.
Co ola io 1.4.7. Sean n, n+1 ∈ Fn. El o den inducido po nen Cn+1 coincide con el o den
na u al de n+1.
Demos ación. Considé ese la cadena ob enida en el eo ema 1.4.5 pa a ci cui os de p o undidad
n+ 1. Es inmedia o comp oba que pa a cualesquie a dos ci cui os consecu i os de dicha cadena,
ambos cumplen que son meno es según el o den inducido po ndesc i o en el lema 1.4.3. Así, el
o den inducido po ncoincide con el de inido po n+1.
18
Po o a pa e, ya que , l y de inen el ci cui o C, podemos ealiza o a ep esen ación ma-
icial del mismo. Es a ep esen ación la denomina emos ep esen ación ma icial dispe sa pa a
di e encia la de la u ilizada en el ejemplo 1.4.12, que enomb a emos como ep esen ación ma icial
compac a. Finalmen e, deno emos de aho a en adelan e ˆ
i,0≤i≤na las unciones índices de Cn,w
que se inducen de mane a na u al po Fn.
Ejemplo 2.1.13. Mos emos las di e en es ep esen aciones de un ci cui o omando m= 6, n = 4
yw= 3.
C0,4
C0,3
C0,2C1,2
C0,1C1,1C2,1
in0in1
Figu a 2.1: Rep esen ación ísica del ci cui o C.








(id, 0,0)
(∨,0,1)
(id, 0,0) (∨,1,2)
(id, 0,0) (∨,0,1) (∧,0,1)
(0) (1)








(a) Rep esen ación ma icial compac a.








001
010
001120
001010011
0 1








(b) Rep esen ación ma icial dispe sa.
Figu a 2.2: Rep esen ación ma icial del ci cui-
o C.
2.2. Índice y espacio cocien e
El obje i o en es e apa ado se á analiza cómo, dado un ci cui o C, ob ene un ci cui o C0 al
que se pa ezca mucho a Cpe o cuyo índice di ie a en 1 en e a C. Sin emba go, aunque pod íamos
de ini la cadena de ci cui os que cumple es a p opiedad, no es lo que amos a hace po una simple
azón: cambia el cableado de un ci cui o es más cos oso que cambia el ipo de una pue a. Po
an o, amos a diseña un algo i mo que eduzca el núme o de cambios de cable que hay que hace
cumpliendo algunas p opiedades esenciales.
De inición 2.2.1. Deno a emos po E|d(C)al conjun o n
S
l=d
El(C).
De inición 2.2.2. Di emos que los ci cui os CyC0es án en la misma clase de equi alencia C|dsi
exis e un enomb amien o en e E|d(C)yE|d(C0)y deno a emos po Cn,w|dal conjun o o mado
po odas es as clases.
En o as palab as, E|d(C)consis e en es ingi las ecuaciones que de inen a Cquedándonos
25

con los dúl imos ni eles y C|dconsis i ía en los ci cui os que ienen los mismos ni eles iguales.
Veámoslo con un ejemplo:
Ejemplo 2.2.3. Conside emos los ci cui os con las siguien es ep esen aciones ma iciales:






010
010221
001111221
0 1 2






Figu a 2.3: Rep esen ación ma icial dispe sa
de C.






010
010221
010020120
0 1 2






Figu a 2.4: Rep esen ación ma icial dispe sa
de C0.
Así, es cla o que C|3=C0|3, C|2=C0|2pe o C|16=C0|1(y en consecuencia C|06=C0|0); solo
bas a mi a ila a ila cada ma iz pa a de ec a es o. 
Obse emos que una clase C|dpuede es a con enida en Cn,w|dpe o ambién en Cn,w0|d. Es o
quie e deci que hay un ci cui o C0en Cn,w0de mane a que C0|d=C|d, o lo que es lo mismo, que
E|d(C) = E|d(C0). Así, hay que ene especial cuidado si se cambia de clase pa a ga an iza que
es a nue a clase iene algún ci cui o con enido en Cn,w (y gene able po minpu s).
No emos aho a algunas elaciones in e esan es. En p ime luga , las clases C|dse pueden e
como elemen os de C|d+1 y la di e encia en e dos elemen os de C|des solamen e los ec o es
= (l0,d, 0,d, ..., lp−1,d, p−1,d)yg= ( 0,d, ..., p−1,d), donde p=|Ed(C)|. En o as palab as, la
di e encia en e dos clases son las pue as y cables del ni el d, y es a in o mación queda plenamen e
ecogida en los ec o es , g. De es a mane a, podemos deno a de mane a cómoda un ci cui o
con la upla de alo es ( j, lj, j), la cual esc ibi emos como j(lj, j)pa a eplica la no ación que
habíamos seguido has a aho a.
A su ez, las clases de Cn,w|dse pueden ag upa en e aquellas que compa en el ec o . A
es as clases las deno a emos ˆ
C|d, al conjun o de las mismas la deno a emos ˆ
Cn,w|dy di emos que
es el ec o asociado a la misma. En consecuencia, enemos el siguien e diag ama conmu a i o,
donde las unciones πconsis en en la p oyección sob e el conjun o imagen.
Cn,w|d+1 ˆ
Cn,w|d+1
Cn,w|dˆ
Cn,w|d
π
π
π
π
Figu a 2.5: Diag ama conmu a i o en e los dis in os conjun os de clases.
Finalmen e, hagamos no a que si ˆ
C|des una clase de ˆ
Cn,w|d, el índice es un o den sob e el
conjun o de elemen os C|d∈ Cn,w|dque son miemb os de ˆ
Cdy, po o a pa e induce un o den
sob e los elemen os de ˆ
Cn,w|d. Po ello, amos a ap o echa la unción índice pa a eco e Cn,w|d
po pa es y en cada pa e segui el o den del índice aunque globalmen e no sea así.
26
2.3. Inc emen o del ipo
Supongamos que es amos den o de una clase ˆ
C|d, donde p=|Ed(C)|y = (l0, 0, ..., lp−1, p−1)
es el ec o asociado a la clase.
P oposición 2.3.1. Dado ec o asociado a ˆ
C|d, el ec o g= ( 0, ..., p)de la clase C|dden o
de ˆ
C|dcumple las siguien es p opiedades:
Si lj= j, en onces j= 1,0≤j < p.
Si lj=lj+1, j= j+1,0≤j < p −1, en onces j= 0 y j+1 = 1.
Demos ación. Si lj= j, en onces la pue a asociada es id, con lo que j= 1. Po o a pa e,
si lj=lj+1 y j= j+1, en onces no puede da se que lj= jdebido a es a en ep esen ación
minimal, ni que Pj=Pj+1, con lo que debido al índice ob enemos que Pj=∨yPj+1 =∧y es o
demues a inmedia amen e la p oposición.
A los alo es de jdel ec o de ipos gque no es én de e minados po la p oposición 2.3.1 los
denomina emos ipos lib es olib es, y los deno a emos en el siguien e algo i mo po τj. Además,
oma emos γ= (τ0, ..., τT)como el ec o de ipos lib es.
Co ola io 2.3.2 (Tipo mínimo).Sea C|dmínimo den o de ˆ
C|dy sea g= ( 0, ..., p)el ec o de
pue as asociado a C|d. En onces γes el ec o nulo.
Demos ación. La demos ación es inmedia a ya que cualquie o o alo de γha ía que el índice
de la clase C0|dcon dicho alo de γ uese mayo .
P oposición 2.3.3. Dado asociado a ˆ
C|dy dado g= ( 0, ..., p−1)asociado a C|d enemos la
siguien e al e na i a:
O bien exis e un único g0= ( 0
0, ..., 0
p−1)asociado a o a clase C0|dcon mismo ec o al
que el índice inducido de C0|ddis a 1del de C|d,
O bien el índice inducido en C|dden o de ˆ
C|des máximo.
Demos ación. Sin pé dida de gene alidad podemos queda nos con el ec o γ= (τ0, ...τT)ya que,
po la p oposición 2.3.1, los alo es que no sean lib es es án de e minados. En onces, si emos γ
como un núme o en bina io, es cla o que el ec o asociado al núme o γ+ 1 es el único ec o que
pod ía cumpli la p ime a al e na i a. Además, pa a que γ+ 1 no es é bien de inido end ía que
da se que γ≡2T−1, y en es e caso es cla o que el índice de C|des máximo.
Ejemplo 2.3.4. Mos a emos de una mane a isual en qué se aduce la p oposición 2.3.3. Se
mues an en neg o los elemen os lj, jde una clase C|n−3(supues o que n > 3), así como los ipos
27
jde C|n−2. Además, se mues an en ojo los elemen os jque no son lib es, en ámba los lib es
al que su ipo es 1y en e de los que ienen j= 0.






011
010121
010230241
030120121221231












011
010121
010230241
031120121221230






Figu a 2.6: Ob ención de C0|n−3a pa i de C|n−3 ía la p oposición 2.3.3.
Se puede e que la clase C0|n−3ob enida p ese a los alo es de los ipos no lib es, y con los
lib es se compo a como un con ado bina io. Además, el colo ámba o o gado a los ipos indica
in ui i amen e que dicho alo no es inc emen able. Po an o, el índice de la clase se á máximo
cuando no haya ningún ipo de colo e de; no pod emos a anza .
Algo i mo 2.3.5 (Inc emen o del ipo).Dado una clase C|dde ˆ
Ckcon ec o asociado g, de uel e
la clase C0|dcuyo ec o asociado es g0y de índice 1mayo que el de C|do de ec a que es imposible
(y de uel e None).
28
Algo i mo 1 Inc emen o del ipo
Requi e: g= [ 0, ..., p−1]
j←p−1
while j≥0∧( jno es lib e ∨ j= 1) do
i jes lib e hen
0
j←0.Si es lib e en onces j= 1 y si exis e g0, 0
j= 0.
else
0
j← j.Si no es lib e y exis e g0, 0
j= j.
end i
j←j−1
end while
i j=−1 hen
e u n None . No exis e g0.
else
0
j←1.Exis e g0y 0
jes lib e, así que 0
j= 1.
end i
e u n g0= [ 0, ... j−1, 0
j, ..., 0
p−1]
Demos ación. La co ección de es e algo i mo es inmedia a g acias a la p oposición 2.3.3.
Como se puede e , el algo i mo iene un cos e máximo de O(p), pe o, po se de ac o un
con ado bina io, el cos e amo izado lo ebaja a O(T+ 1), donde Tes el núme o de lib es en ˆ
C|d.
En de ini i a, hemos conseguido eco e la clase ˆ
C|dinc emen ando en cada paso el ec o ipo un
poco, de ahí el nomb e del algo i mo.
2.4. La p opiedad del buen p e ijo
Nues o siguien e obje i o se á, ijada la clase ˆ
C|d+1 eco e las clases de ˆ
Cn,w|dsiguiendo el
o den del índice. Pa a ello nos ald emos de la p opiedad del buen p e ijo, la cual expond emos en
es a sección. Así, supongamos que d > 0y deno emos p=|Ed(ˆ
C)|yk=|Ed−1(ˆ
C)|; y omemos una
clase ˆ
C|dy su ec o asociado, el cual iene amaño 2p. Tengamos en cuen a que el obje i o de
es a sección es busca una clase ˆ
C0|d al que |Ed(ˆ
C0)|=p,|Ed−1(ˆ
C)|=kde mane a que podamos
pasa cómodamen e de ˆ
C|daˆ
C0|d.
De inición 2.4.1. Di emos que j∈Zes un alo álido si 0≤j < k.
De inición 2.4.2. Dado un ec o 0= (l0, 0, ...lj, j)deno a emos po Sj,−1≤j < p al conjun o
de es an es Sj=Zk {li, i|0≤i≤j}y denomina emos a 0el ec o complemen o de Sj.
In ui i amen e, dada una colección de alo es {l0, 0, ...lj−1, j−1},Sj ep esen a los índices de
los ci cui os que al an po añadi a un ec o 0asociado a alguna clase ˆ
C|kde mane a que es é
29
bien o mada, es o es, que u ilice odos los ci cui os del ni el in e io al menos una ez. Po ello,
S−1={i|0≤i<k}ySp−1=∅. No malmen e, y mien as no se diga nada, oma emos como
ec o complemen o el j= (l0, 0, ..., lj, j), esul an e de es ingi nos a las 2(j+ 1) p ime as
componen es del ec o asociado a ˆ
C|d.
Lema 2.4.3. Si es un ec o de amaño 2pasociado a una clase ˆ
C|d, en onces Sp=∅.
Demos ación. Si Sp6=∅, en onces no puede es a asociado a ninguna clase de ˆ
C|dya que en ese
caso al a ían ci cui os de Ed−1(ˆ
C)po u iliza .
De inición 2.4.4. Di emos que 0= ( 0
0, ..., 0
)es un p e ijo de = ( 0, ..., s), con ≤ssi 0
j= j
pa a odo 0≤j≤ y llama emos núme o de huecos ah( , 0) = s− .
Además, dado = ( 0, ..., )deno a emos po +αal ec o ( 0, ..., , α).
Lema 2.4.5 (Fal a de huecos).
1. Si 0= (l0, 0, ...lj, j)es un p e ijo de y si αes un alo álido al que 0+αsea p e ijo de
un ec o 00 de amaño 2pasociado a alguna clase ˆ
C0|d, en onces |Sj {α}| ≤ h( , 0+α).
2. Si 0= (l0, 0, ...lj, j, lj+1)es un p e ijo de y si αes un alo álido al que 0+αsea p e ijo
de un ec o 00 de amaño 2pasociado a una clase ˆ
C0|d, en onces |Sj {lj+1, α}| ≤ h( , 0+α).
Demos ación.
1. Si se diese que |Sj {α}| > h( , 0+α), en onces de ninguna mane a el ec o 00 cumpli ía
que Sp=∅, lo cual con adi ía el lema 2.4.3.
2. Análoga al apa ado an e io .
Lema 2.4.6 (Exceso de huecos).Sea 0= (l0, 0, ...lj, j)un p e ijo de y sean λ≤ρdos alo es
álidos. Si 0+λ+ρes p e ijo de un ec o 00 de amaño 2pasociado a alguna clase ˆ
C0|d, en onces
2(k2−1−ˆ
n(ˆ
C)) ≥h( , 0+λ+ρ), donde ˆ
C:=τ(λ, ρ)yτ= 1 si λ=ρy0en o o caso.
Demos ación. Po la p oposición 2.1.4, solo hay k2−1−ˆ
n(ˆ
C)ci cui os gene ables a pa i de los
kexis en es que engan índice mayo que ˆ
C. Además, cada ci cui o emplea 2a gumen os, con lo
que el máximo núme o de alo es que se pueden añadi al p e ijo 0+λ+ρes 2(k2−1−ˆ
n(ˆ
C)). Y
es e alo debe se al menos h( , 0+λ+ρ). Nó ese que se oma τ= 0 si λ6=ρpa a que el ci cui o
1(λ, ρ)pueda conside a se ambién.
Tengamos en cuen a que el nomb e de los lemas 2.4.5 y2.4.6 ienen dados po la negación de
los mismos. Así, si no hay su icien es o hay demasiados huecos, es cla o que al añadi los alo es
álidos no podemos ob ene un ec o 00 alido pa a alguna clase ˆ
C|d.
30

Lema 2.4.7 (Tes izquie do).Sea 0= (l0, 0, ...lj, j)un p e ijo de y sea λun alo álido. Si
0+λes p e ijo de un ec o 00 asociado a alguna clase ˆ
C|den onces o bien ˆ
Sj=Sj {λ}=∅o
bien λ < m´ın{ˆ
Sj}.
Demos ación. Si ˆ
Sj6=∅, en onces sea ρ= m´ın ˆ
Sj. Como λ6=ρ, en onces λ<ρ, ya que en caso
con a io el ci cui o C:=P(C1, C2) al que l=λ, =ρcumpli ía que l > y en onces no es a ía
bien conec ado; lo cual se con adice con las p opiedades de nues o conjun o Cn.
G acias a es os lemas, hemos podido ap ecia p opiedades que deben cumpli los alo es λy
ρcon los que que emos ex ende nues o p e ijo. Con los siguien es eo emas e emos que es as
p opiedades no solo son necesa ias sino que ambién son su icien es.
Teo ema 2.4.8 (P opiedad del buen p e ijo - de echo).Sea el ec o asociado a ˆ
C|d, sea 0=
(l0, 0, ..., lj+1)y sea ρ≥lj+1 un alo álido al que 1(lj, j)< τ(lj+1, ρ), con τ= 1 si lj+1 =ρy
0en o o caso. En onces 0+ρes un p e ijo de algún ec o 00 asociado a alguna clase ˆ
C0|dsi y
solo si se dan las siguien es condiciones:
|Sj {lj+1, ρ}| ≤ h( , 0+ρ).
2(k2−1−ˆ
n(τ(lj+1, ρ))) ≥h( , 0+ρ), donde τ= 1 si lj+1 =ρy0en o o caso.
Demos ación.
=⇒Es consecuencia inmedia a de los lemas 2.4.5 y2.4.6.
⇐=Si 2(k2−1−ˆ
n(τ(lj+1, ρ))) ≥h( , 0+lj+1 +ρ)en onces hay al menos una colección de
alo es V={li, i|j+ 1 < i < p}o denada ía el índice de mane a que odos los ci cui os de V
sean dis in os. Po o a pa e, al se 0asociado a , se cumple que o bien Sj {lj+1, ρ}es acío o
bien lj+1 <m´ın Sj {lj+1}.
Si es acío, omemos V0=Vy p ocedamos al el pá a o siguien e. Si no, ya que |Sj {lj+1, ρ}| ≤
h( , 0+ρ), podemos oma los ci cui os (si, si+1), si, si+1 ∈Sj, con Sjo denado ía el índice
( omando (si+1, si+1)en el caso de que sean impa es) y sus i ui es os cs =b1
2(|Sj {lj+1, ρ}|+1)c
ci cui os po cualesquie a cs pa ejas de alo es de Vob eniendo V0.
De es a mane a, o denando V0 ía el índice y omando 00 = 0+ρ+V0, es cla o que 00 es á
bien o mado ya que a lo sumo hay un pa de índices i, i + 1 ales que (li, i) = (li+1, i+1)pa a
cada upla (l, )y u iliza odos los ci cui os de Ed−1(ˆ
C). En consecuencia, es un ec o asociado a
alguna clase ˆ
C0|dy 0+ρes p e ijo de él.
Teo ema 2.4.9 (P opiedad del buen p e ijo - izquie do).Sea el ec o asociado a ˆ
C|d, sea
0= (l0, 0, ..., lj, j), con j < p −1y sean λ, ρ alo es álidos ales que λ≤ρy ales que 1(lj, j)<
τ(λ, ρ), con τ= 1 si λ=ρy0en o o caso. En onces 0+λ+ρes un p e ijo de algún ec o 00
asociado a alguna clase ˆ
C0|dsi y solo si se dan odas las condiciones siguien es:
|Sj {λ, ρ}| ≤ h( , 0+λ+ρ).
31
2(k2−1−ˆ
n(τ(λ, ρ))) ≥h( , 0+λ+ρ), donde τ= 1 si λ=ρy0en o o caso.
O bien Sj {λ}=∅, o bien λ≤m´ın Sj.
Demos ación.
=⇒Es consecuencia inmedia a de los lemas 2.4.5,2.4.6 y2.4.7.
⇐=Si 2(k2−1−ˆ
n(τ(λ, ρ))) ≥h( , 0+λ+ρ)en onces hay al menos una colección de alo es
V={li, i|j+ 1 < i < p}o denada ía el índice de mane a que odos los ci cui os de Vsean
dis in os. Po o a pa e, po la e ce a condición, o bien Sj {λ}=∅, o bien λ≤m´ın{Sj}.
Así, de inido Vy g acias a la e ce a condición podemos p ocede de mane a análoga al eo ema
an e io pa a ob ene un V0 al que 00 = 0+λ+ρ+V0sea un ec o asociado a alguna clase ˆ
C0|d
y en consecuencia, 0+λ+ρes p e ijo de 00.
Co ola io 2.4.10 (Mínimo ρ).En las condiciones del eo ema 2.4.9, si h( , 0+λ)>|Sj {λ}|,
podemos oma ρ=λ. Si no, y supues o que {s∈Sj|s>λ} 6=∅, el alo ρ= m´ın{s∈Sj|s > λ}
sa is ace el eo ema pa a dicho λ. Además, es e ρes el mínimo alo ob enible que sa is ace el
eo ema pa a dicho alo de λ.
Demos ación. En p ime luga no emos que la e ce a condición del eo ema no se e a ec ada po
es e esul ado al no depende de ρ. Así, si h( , 0+λ)>|Sj {λ}|, en onces h( , 0+λ+λ)≥ |Sj {λ}|,
lo cual equi ale a la p ime a condición. Además, es cla o que no hay meno ρque pe mi a que τ(λ, ρ)
es é bien conec ado. Finalmen e, po la de inición del índice, la co a supe io de los huecos cumple
que 2(k2−1−ˆ
n(τ(λ, ρ))) ≤2(k2−1−ˆ
n(τ(λ, λ))). Es deci , si hay algún alo ρque posibili a
que se cumpla el eo ema pa a dicho 0y dicho λ, es e debe se ρ=λ.
Sin emba go, si h( , 0+λ)≤ |Sj {λ}|, en onces no se cumple la p ime a condición con dicho ρ.
De hecho, no se cumpli á pa a ningún ρque no es é en Sj {λ}. Po ello, ρdebe es a en Sj {λ}.
Además, pa a que es é bien conec ado, ρ≥λ, po lo que, u ilizando la segunda condición de nue o,
en el caso de habe un ρque cumpla las condiciones del eo ema pa a es e λ,ρ= m´ın{s∈Sj|s > λ}
las cumpli á, con lo que es a de inición de ρlo hace mínimo.
No emos que si h( , 0+λ)≤ |Sj {λ}| y{s∈Sj|s > λ}=∅, en onces hemos p obado además
que el ec o 0+λno es p e ijo de ningún 00 asociado a alguna clase ˆ
C0|d.
Algo i mo 2.4.11 (P opiedad del buen p e ijo).Dado = (l0, 0, ..., lp−1, p−1) ec o de ˆ
C|d,j
en e o al que 0≤j < p,Sjyρoλsegún p oceda, de uel e si 0= (l0, 0, ..., lj, j, λ, ρ)cumple la
p opiedad de buen p e ijo.
32
Algo i mo 2 P opiedad del buen p e ijo
Requi e: Sj, λ oρyh( , 0).
i λno es None hen
Comp oba el lema Tes izquie do .Si no se da, de uel e alse.
Ob ene ρusando el co ola io Mínimo ρ.Si no exis e, oma el alo None.
else
λ←lj+1 .Si ρ<lj+1, oma el alo None.
end i
i λoρes None hen
e u n alse
else
Comp oba los lemas Fal a de huecos yExceso de huecos .Si no se dan, de uel e alse.
e u n ue .Se cumplen odas las condiciones del buen p e ijo.
end i
Demos ación. La demos ación se sigue de los eo emas 2.4.8,2.4.9 y del co ola io 2.4.10.
Nó ese que dado j, el cos e de ob ene h( , 0)suele se cons an e en la mayo ía de los lengua-
jes de p og amación. Así, suponiendo que Ses un conjun o implemen ado con un mon ículo que
enemos calculado p e iamen e, el cos e de alida los lemas 2.4.5 y2.4.7 es á en O(log(p)) al igual
que el cos e del co ola io 2.4.10. Finalmen e, el cos e de comp oba el lema 2.4.6 es cons an e, con
lo que el cos e de es e algo i mo es del o den de O(log(p)).
Recapi ulando b e emen e es a sección: dado un ec o asociado a una clase ˆ
C|dy un a-
lo λ( espec i amen e ρ) hemos ob enido un es pa a sabe si exis e un p e ijo de amaño 2j
( espec i amen e 2j+ 1) de de mane a que ambién lo sea de un ec o 0dis in o.
2.5. Inc emen o del cableado
G acias a la p opiedad del buen p e ijo y dado un ec o asociado a una clase ˆ
C|d, a a emos
de ob ene o o ec o 0asociado a o a clase ˆ
C0|dde mane a que ˆ
C|d+1 =ˆ
C0|d+1. Además,
mos a emos cómo pode hace lo de mane a que el índice en e ambas clases dis e 1. En es a
sección pond emos el oco en cómo ob ene ˆ
C0|d al que |Ed(ˆ
C)|=|Ed(ˆ
C0)|=py|Ed−1(ˆ
C)|=
|Ed−1(ˆ
C0)|=k, si es o es posible; donde pykse de inen como en la sección an e io .
Lema 2.5.1 (Siguien e de echo).Sea
j= (l0, 0, ..., lj). Si ni ρ0= j+ 1 ni ρ00 = m´ın{s∈
Sj−1|s> j}(supues o que {s∈Sj−1|s> j} 6=∅) son alo es álidos con los que se cumple la
p opiedad del buen p e ijo, en onces no exis e ningún ρ> jque lo pe mi a.
Demos ación. En p ime luga no emos que si j+ 1 no es álido, no exis e ρ> jque sea álido,
con lo que sin pé dida de gene alidad supongamos que j+ 1 es álido. Además, po se
jp e ijo
de , se da que j≥lj.
33
Así, azonemos po con adicción. Sea ρdis in o a ambos alo es. Si ρ0no cumple las condiciones
del eo ema, es po que o bien 2(k2−1−ˆ
n(0(lj, ρ0))) < h( ,
j+ρ0)o bien |Sj−1 {lj, ρ0}| >
h( ,
j+ρ0). Si es po que se da que 2(k2−1−ˆ
n(0(lj, ρ0))) < h( ,
j+ρ0), es cla o que no exis e
ningún ρadmisible, ya que ˆ
n(0(lj, ρ0)) <ˆ
n(0(lj, ρ)) y en consecuencia el lema 2.4.6 no se cumpli á
pa a ningún alo ρ.
Po an o, podemos supone que lo que acon ece es que |Sj−1 {lj, ρ0}| > h( ,
j+ρ0). Así, pa a
cualquie ρ al que |Sj−1 {lj, ρ}| =|Sj−1 {lj, ρ0}| se a a da que |Sj−1 {lj, ρ}| > h( ,
j+ρ); con
lo que de exis i dicho ρ, es e iene que es a en Sj−1 {lj}. Además, ρ> j, con lo que debe es a
en ˆ
Sj−1={s∈Sj−1 {lj} | s > j}. Si ˆ
Sj−1=∅, hemos acabado la demos ación. Si no, podemos
oma ρ00 como en el enunciado del eo ema, y, ya que ρ≥ρ00 ≥ρ0, podemos azona como en el
pá a o an e io pa a deduci que debe da se que |Sj−1 {lj, ρ00}| > h( ,
j+ρ00)si exis e dicho
alo ρ. Así, ya que |Sj−1 {lj, ρ00}| =|ˆ
Sj−1|+ 1 = |Sj−1 {lj, ρ}|, es cla o que ρincumple el lema
2.4.5.
Es e esul ado es muy impo an e ya que nos dice que dado 0de amaño impa , solo nos bas a
con p oba dos alo es de ρpa a e si 0+ρes p e ijo de un ec o 00 asociado a alguna clase ˆ
C0|d.
Lema 2.5.2 (Siguien e izquie do).Sea l
j= (l0, 0, ..., lj−1, j−1). Si ni λ0=lj+1 ni λ00 = m´ın{s∈
Sj−1|s>lj}(supues o que {s∈Sj−1|s>lj} 6=∅) son alo es álidos con los que se cumple
la p opiedad del buen p e ijo independien emen e del ρ, en onces no exis e ningún λ > ljque lo
pe mi a.
Demos ación. Po el co ola io 2.4.10, es cla o que solo enemos que p oba lo con dos alo es
candida os a ρ. La demos ación es análoga al lema 2.5.1 eniendo en cuen a además que hay que
ene en cuen a la sa is acibilidad del lema 2.4.7.
Lema 2.5.3 (Siguien e izquie do simpli icado).Sea l
j= (l0, 0, ..., lj−1, j−1). Si λ0=lj+ 1 no
es un alo álido con el que se cumple la p opiedad del buen p e ijo independien emen e del ρ,
en onces no exis e ningún λ>ljque lo pe mi a.
Demos ación. Po el lema 2.5.2, nos bas a p oba que si λ0=lj+ 1 no es un alo admisible pa a
el ec o 0, en onces λ00 = m´ın{s∈Sj−1|s > lj}no lo es ampoco pa a 0, ya que en caso de que
se dé que {s∈Sj−1|s>lj}=∅dicho lema nos ga an iza el esul ado.
Así, azonemos po con adicción: supongamos que exis e un ρ≥λ00 al que 0+λ00 +ρes
p e ijo de 00. En onces, como ρ≥λ00 > λ0, es cla o que se cumple el lema 2.4.6 pa a λ00, ρ y 0.
Ya que se cumple el lema 2.4.7 pa a λ, puede sucede que Sj−1=∅, o bien Sj−1={λ00}, o bien
λ00 ≤m´ın Sj−1. En el p ime caso, es cla o que se cumple dicho lema pa a λ0, y en los o os dos
podemos plan ea la desigualdad λ0< λ00 ≤m´ın Sj−1; con lo que si λ00 cumple el lema 2.4.7,λ0
ambién.
34
mínimo de h0 2 0 5 1 5 3 4ies 0=h0 2 1 i(comp uébese). Po el co ola io 2.4.10
y el eo ema 2.4.8, sabemos que cualquie ρdel cual 0+ρsea p e ijo cumple que j= 1. Po ello,
00 iene de p e ijo a 0=h0 2 1 1i.
En onces, dado que h( 00, 0) = 4 = |S0
1|+ 1, es amos en las hipó esis del lema 2.5.8. Los alo es
ob enidos po el lema 2.5.6 son λ0= 1, ρ0= 2, con lo que es amos en el subcaso 2de dicho lema.
Po ello, sabemos que 00 iene po p e ijo 0+λ+σ, donde λ=λ0= 1 yσ= m´ın{s≥ρ0, s ∈S0
j}=
m´ın{3,4,5}= 3.
En la siguien e e apa del algo i mo sabemos que 0=h0 2 1 1 1 3ies p e ijo de 00.
Además, h( 00, 0)=2=|Sj|, con lo que es amos en las hipó esis del lema 2.5.9. Así, es cla o que
00 = 0+ 4 + 5 ya que h( 00, 0+ 4 + 5) = 0.
Ejemplo 2.5.12. Comp uébese que el ec o 00 del cual es p e ijo el ec o 0del ejemplo 2.5.5 es
00 =h0 3 1 4 2 5 6 7i(lo cual es inmedia o al cumpli se el lema 2.5.9 con 0). 
Además, obse emos que no hemos hablado de a ia los inpu s. Es deci , es os lemas suponen
que d≥1y en de ini i a, como mos a emos, nos pe mi i á ob ene un ci cui o bien de inido sob e
un conjun o de k=|E0(C)| ≤ minpu s. Sin emba go, no hemos hablado de cómo selecciona
es a can idad. La espues a es muy simple: dado un subconjun o Sde {i|0≤i<m} al que
|S|=k, podemos o dena los elemen os de dicho conjun o ía el índice. Los elemen os p esen es
en Sde e minan uní ocamen e qué inpu s pode elegi y, ya que es o no p esen a ningún ipo de
complicación écnica, pod emos supone que con amos con un mé odo que nos pe mi e cambia de
inpu s sin cambia la es uc u a del ci cui o.
Finalmen e, no emos que as ob ene 00 median e es e algo i mo, podemos aplica el co ola io
2.3.2 pa a ob ene el mínimo ec o gasociado a ˆ
C0|dy así de ini la clase C0|d∈ Cn,w|d. Además
no emos que en odo el p oceso ealizado no hemos pe dido in o mación, es o es, dado C|dpodemos
ob ene C0|dde mane a que odos los ni eles no a ec ados po la eo ía mencionada an e io men e
no cambian. Po ello, podemos isualiza ˆ
C|dcomo una abs acción pa a simpli ica los cálculos de
la cual podemos ol ida nos de mane a p ác ica.
Recapi ulando ideas: hemos conseguido un algo i mo que nos pe mi e, dada una clase ˆ
C|d,
de ec a si hay alguna clase ˆ
C0|dsiguien e a ˆ
C|dde mane a que ˆ
C|d+1 =ˆ
C0|d+1 (g acias a la
p opiedad del buen p e ijo); y en caso a i ma i o, cons ui la.
2.6. Ampliación del suelo, cambio de ni el y in del algo i mo
Sin emba go, pod ía sucede que la clase ˆ
C0|dque dis a 1de ˆ
C|d, donde ˆ
C|d+1 =ˆ
C0|d+1 den o de
ˆ
Cn,w|d+1 no cumpliese que |Ed−1(ˆ
C0)|=|Ed−1(ˆ
C)|. En ese caso, end ía que da se que |Ed−1(ˆ
C0)|=
|Ed−1(ˆ
C)|+ 1 ya que si exis e j, d ≤j≤n al que|Ej(ˆ
C)| 6=|Ej(ˆ
C0)|, en onces ˆ
C|d+1 6=ˆ
C0|d+1.
Po el lema 2.1.4, el co ola io 1.3.3 y la de inición de ˆ
Cn,w, sabemos que es o solo se puede da si
|Ed−1(ˆ
C)|<m´ın{2p, w, δm(d)}.
41

Lema 2.6.1 (Vec o mínimo).Dado d≥1y una clase ˆ
C|d+1 ∈ˆ
Cn,w|d+1 con n > 1 al que
p=|Ed(ˆ
C)|yk=|Ed−1(ˆ
C)|, en onces exis e un único ec o d−1(asociado a una única clase
ˆ
C0|d) de mane a que ˆ
C0|dsea mínima den o de ˆ
C|d+1.
Demos ación. Po la de inición de bien conec ado y la unción índice es cla o que (0) es p e ijo de
cualquie ec o . Así, g acias al co ola io 2.4.10 exis e un ρ al que 0= (0, ρ)es el mínimo p e ijo
de amaño 2. En conc e o, es e ec o es p e ijo del mínimo ec o de asociado a alguna clase ˆ
C|d.
Aplicando el algo i mo 2.5.10 podemos ex ende 0has a . La unicidad se da del de e minismo del
algo i mo.
Teo ema 2.6.2 (Ampliación del suelo).Exis e 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
algo i mo 2.5.10 de uel e None pa a ˆ
C|d.
Demos ación.
=⇒Sea ˆ
C0|d al que |Ed(ˆ
C0)|=k+ 1. Po el lema 2.1.4 se iene que k+ 1 ≤2py po el co ola io
1.3.3 se da que k+ 1 ≤δm(d−1). Además, po la de inición de ˆ
Cn,w es cla o que k+ 1 ≤w.
En de ini i a, k+ 1 ≤m´ın{w, δm(d),2p}. Po an o, k < m´ın{w, δm(d−1),2p}. Finalmen e, el
algo i mo 2.5.10 debe de ol e None ya que el índice en e ˆ
C0|dyˆ
C|ddis a 1y no se cumple que
|Ed−1(ˆ
C)|=|Ed−1(ˆ
C0)|.
⇐=Si el algo i mo 2.5.10 de uel e None pa a ˆ
C|dsigni ica que la siguien e clase ˆ
C0|d, de
exis i , cumple que |Ed−1(ˆ
C0)|> k. Como k < m´ın{w, δm(d−1),2p}, omemos k0=k+ 1 y
comp obemos que exis e una clase ˆ
C0|d al que |Ed−1(ˆ
C0)|=k0, ya que si k00 > k0, la clase ˆ
C00|d
den o de ˆ
C|d+1 end á mayo índice.
De hecho, nos bas a p oba que exis e una clase ˆ
C0|d∈ˆ
C|d+1 al que |Ed−1(ˆ
C0)|=k0, ya que
po el lema 2.6.1, en onces dicha clase mínima exis i ía. Así, omemos 0= (0) y comp obemos que
se cumple la p opiedad del buen p e ijo pa a algún 00. Tomando ρ= 1, pues o que |S0
−1 {0,1}| =
k0−2 = k−1 = |S−1| − 1, en onces |S0
−1 {0,0}| =|S−1| − 1≤2(p−1) = h( 00, 0+ρ)pa a
cualquie 00 de amaño 2p. Con lo que se cumple el lema 2.4.5.
Po o a pa e, ya que ˆ
C|des una clase, en onces el ec o ˜ 0= (0) es p e ijo de su ec o ˜
asociado y se cumple el lema 2.4.6. Es deci , 2(p−1) = h(˜ , ˜ 0+ 0)≤2(k2−1−ˆ
n(τ(0, 0))) ≤
2(k2−1). Comp obemos que dicho lema se cumple ambién pa a 0:2(k02−1−ˆ
n(1(0,0))) =
2(k2+ 2k+ 1 −1−0) = 2(k2+ 2) ≥2(k2−1) ≥2(p−1). Po ello, 0cumple el eo ema 2.4.8 y en
consecuencia exis e un ec o 00 asociado a ˆ
C0|d. Finalmen e, nos queda comp oba que dicha clase
es á en ˆ
Cn,w y es u o de un ci cui o con minpu s, cosa que en el es o de lemas an e io es e a algo
cla o y e iden e ya que el núme o de pue as en la clase ˆ
C|de a in a ian e a las ans o maciones
ealizadas.
Pa a p oba lo, p obemos en p ime luga que pe enece a ˆ
Cn,w|d. Pa a ello, hay que p oba que
exis e ˆ
Den ˆ
Cn,w al que ˆ
D|d=ˆ
C0|d. Pues o que C∈ Cn,w, en onces exis e un alo l, al que
42
|El(C)|=w, y es e no puede se dpo hipó esis. Así, si exis e un l > d al que |El(C)|=w,
en onces |El(C0)|=wy hemos acabado. Si no, necesa iamen e exis e un l < d al que |El(C)|=w.
P oba emos que exis e una clase ˆ
C|l∈ˆ
C|d, con |El(C)|=wy lo ha emos de mane a cons uc i a,
ob eniendo pa a cada j, l < j < d un ec o jde mane a que dichos de inan la clase ˆ
C|d.
Po la p oposición 2.1.4 sabemos que si en el ni el jhay kjpue as, en el ni el j+1 hay al menos
η(kj)pue as. Así, de inamos kj= m´ax{k+ 1, ηj−l(w)}, l ≤j≤d. Ya que k < k + 1 yCes un
ci cui o se da necesa iamen e 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 mane a ob ia ob enemos que kj≤kj−1.
En onces se da la siguien e causís ica pa a odo alo j, l < j < d:
kj=kj−1=k+ 1. Tomemos en es a si uación el ec o j= (0,0,1,1, ..., k, k). En onces,
podemos de ini la clase ˆ
C0|jcomo ˆ
C0|j+1 ∪ { j}. 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. Po la p oposición 2.1.4 sabemos que se da la siguien e
desigualdad kj< kj−1≤2kj. Así, deno emos p= 2kj−kj−1>0y de inamos el ec o
j−1= (0,0,1,1..., p −1, p −1, p, p +1, ..., kj−1). Es cla o que es un ec o de amaño 2kjy se
cumple que apa ecen odos los elemen os en e 0ykj−1, con lo que la clase ˆ
C0|j=ˆ
C0|j+1∪{ j}
es á bien de inida 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 es e caso o bien 2kj=kj−1, con lo que de inamos
j= (0,1,2, ..., kj−1)o bien 2kj−1 = kj−1, en cuyo caso de inamos j= (0,0,1,2, ..., kj−1). En
ambos casos jes un ec o de amaño 2kjy podemos de ini la clase ˆ
C0|jcomo ˆ
C0|j+1 ∪{ j},
de mane a que |Ej(ˆ
C0|j)|=|Ej(ˆ
C0|j+1)|=kjy|Ej−1(ˆ
C0|j)|=kj−1.
En cualquie caso, es cla o que podemos ob ene la clase ˆ
C0|l+1 a pa i de ˆ
C0|dcumpliendo que
|El(ˆ
C0)|=wyˆ
C0|l+1 ∈ˆ
C0|d. Po an o, ˆ
C0|d∈ˆ
Cn,w|d. Además, ya que |El(ˆ
C0|l+1)|=|El(C)|=w,
es cla o que w≤δm(l−1). Queda po p oba pues que hay un ci cui o en esa clase gene able
median e minpu s.
De inamos kl=|El(ˆ
C0)|(con l=d−1en el caso de que ˆ
C0|d u iese un ni el i>d al que
|Ei(D)|=w); y pa a odo j, 0≤j < l esc ibamos kj=σ(kj+1). Así, p obemos que si enemos
de inido ˆ
C0|j+1, podemos de ini ˆ
C0|jde mane a que |Ej−1(ˆ
C0|j)|=kj−1ykj−1≤δm(j−1).
De hecho, nos enca ga emos de da un ec o jcon el que de ini dicha clase. Tomemos 0=
(0,0). Po el lema 2.5.6 exis en li+1, i+1 de mane a que dado el ec o (l0, 0, ...li, i)se dé que
j(τ(li, i)) + 1 = j(τ0(li+1, i+1)), donde τ= 1 si li= ioi > 0, li−1=li, i−1= iy0en o o
caso y τ0= 1 si li+1 = i+1 o si li=li+1, i= i+1 y0en o o caso. Así, y ya que l0= 0= 0
y j(1(0,0)) = 0 podemos de ini un ec o de amaño 2kjen el que apa ezcan odos los é minos
i, 0≤i<kj−1ya que se da que (kj−1−1)2< kj≤k2
j−1(p oposición 2.1.4).
Finalmen e, ya que k2
j−1≤kj≤δm(j), en onces k2
j−1≤pδm(j) = √m2j=m2j−1=δm(j−1).
Repi iendo el a gumen o un núme o ini o de eces ob enemos que hemos de inido una clase ˆ
C0|0
de mane a que k0≤δm(0) = m. Po an o, la clase ˆ
C0|l+1 pe enece a ˆ
Cn,w|ly en consecuencia es o
43
mismo sucede pa a ˆ
C0|d.
Sin emba go, pod ía da se que exis ie a una clase ˆ
C0|dde índice mayo que el de ˆ
C|dque no
cumpliese que ˆ
C|d+1 =ˆ
C0|d+1. En ese caso es po que el índice de ˆ
C|dinducido en ˆ
C|d+1 es máximo;
es deci ˆ
C|des la úl ima clase de ˆ
C|d+1. En es e caso, sabemos que dicha clase iene que cumpli
que ˆ
C0|d+1 dis e 1de ˆ
C|d+1 y de mane a ecu si a podemos aplica las he amien as que hemos
desa ollado en es a sección pa a ob ene una clase ˆ
C0|j al que ˆ
C|jdis e 1.
Combinando es os dos lemas jun o al algo i mo 2.5.10 pod emos a anza den o de ˆ
C|d+1 de
mane a cómoda y na u al, al y como se puede e en el ejemplo siguien e.
Ejemplo 2.6.3. Sea ˆ
C|n−3∈ Cn,w la clase con ep esen ación ma icial dispe sa siguien e (supues o
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


Figu a 2.9: Ejemplo de cambio de ni el.
Obse emos que la clase ˆ
C|n−3cumple que |En−4(ˆ
C)|= 6 ya que los alo es dis in os de la
úl ima ila son lo que de e mina dicho alo . En es as condiciones, el algo i mo 2.5.10 de uel e
None y el eo ema 2.6.2 no se cumple ya que k= m´ın{6, w, δm(n−4)}. Po an o, nos ol idamos
de ˆ
C|n−3y pasamos a conside a ˆ
C|n−2, de lo que da e el colo g isáceo que oma la ila n−3.
En es e caso, el algo i mo 2.5.10 uel e a da None, pe o es a ez sí se cumple el eo ema 2.6.2
ya que 3<m´ın{2·2, w, δm(n−3)}= 4. Po an o sabemos que la nue a clase ˆ
C0|n−2cumple
que |En−2(C0)|= 2,|En−3(C0)|= 4. U ilizando el lema 2.6.1, podemos ácilmen e ob ene que
n−3=h0 1 2 3i.
Como se ha podido e , a eces es necesa io comp oba de mane a sucesi a dicho lema pa a
pode ob ene la siguien e clase. Además, en cada subida, pe demos in o mación sob e la es uc u a
del es o de ni eles, in o mación que de alguna mane a end emos que ecupe a de nue o.
Co ola io 2.6.4 (Fin del algo i mo).Si |En−1(ˆ
C)|= m´ın{2p, w, δm(n−1)}y no exis e ˆ
C0|n−1
al que la di e encia de índices con ˆ
C|n−1dis e 1, en onces no exis e ningún ci cui o ˆ
C0de índice
44
mayo que ˆ
Cen ˆ
Cn,w.
Demos ación. Se deduce i ialmen e del eo ema 2.6.2 con d=n.
2.7. Re o no a los ci cui os: ep esen an e mínimo y ci cui o
inicial
Todos los esul ados an e io es nos ayudan a a anza en Cn,w con la abs acción de las clases.
Sin emba go, el obje i o inicial e a abaja con ci cui os, no con clases. Así, a a emos de, una
ez ob enida una clase, ecupe a el mínimo ci cui o de dicha clase. En p ime luga , no emos que
odo ci cui o Ces equi alen e a C|0. Po ello, nos bas a con ene un mé odo pa a descende en e
clases de mane a que dado C|del ep esen an e C|d−1sea mínimo den o de C|d. De hecho, nos
bas a con analiza lo desde ˆ
Cn,w|dya que podemos aplica el co ola io 2.3.2 en e cada ep esen an e
ˆ
C|dpa a ob ene la minimalidad (es u ina io comp oba lo u ilizando el índice).
Lema 2.7.1. Sea Cun ci cui o de p o undidad n > 1y anchu a a bi a ia y sean d, d0≥0, d > d0,
k=|Ed(C)|, k0=|Ed0(C)| al que ηd−d0(k0)≤kyσd−d0(k)≤k0. En onces exis e una clase
ˆ
C0∈ˆ
Cn|d0que cumple que ˆ
C0|d+1 =ˆ
C|d+1 y que pa a odo l, d0≤l≤dse da que |El(ˆ
C0)|=kl,
donde kl= m´ax{σd−l(k), ηl−d0(k0)}. Además el índice de es a clase (ob enido al compa a clases de
Cn|d0den o de ˆ
C|d+1) es mínimo.
Demos ación. En p ime luga no emos σ(z)≤zyη(z)≤zpa a cualquie z≥0y que kd=k
yk0
d=k0. G acias al co ola io 2.1.5 sabemos que |El(C)| ≥ σd−l(k). Po o a pa e, aplicando
la p oposición 2.1.4 de mane a sucesi a, ob enemos que |El(C)| ≥ ηl−d0(k0). Po ello, |El(C)| ≥
m´ax{σd−l(k), ηl−d0(k0)}. Además, del hecho de que Csea un ci cui o, es cla o que podemos oma
el es o de ni eles de C0no mencionados en el lema idén icos a C. Finalmen e, g acias de nue o a
la p oposición 2.1.4, es cla o que una clase que cumpla que |El(ˆ
C)|=kly|El−1(ˆ
C)|=kl−1es á
bien de inida.
El además es cla o g acias a la aplicación ei e ada del lema 2.6.1 pa a odo l6= 0 y del de
meno subconjun o si l= 0; eniendo en cuen a que odos los esul ados mencionados se aplican
independien emen e de la anchu a del ci cui o (aunque las usemos siemp e con es icción).
Co ola io 2.7.2 (Ex ensión mínima).Sea Cun ci cui o en Cn,w y sean d, d0≥0, d > d0,k=
|Ed(C)|, k0=|Ed0(C)| al que ηd−d0(k0)≤kyσd−d0(k)≤k0y pa a algún ni el d00 de la o ma d00 ≥d
od00 ≤d0se da que |Ed00 (C)|=w. En onces exis e una clase ˆ
C0∈ Cn,w|d0que cumple que ˆ
C0|d+1 =
ˆ
C|d+1 y que pa a odo 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 es a clase (ob enido al compa a clases de Cn,w|d0den o de ˆ
C|d+1) es mínimo.
45
Demos ación. Po el lema 2.7.1 sabemos que kl≥m´ax{σd−l(k), ηl−d0(k0)}y po la obse ación
ealizada en dicho lema, kl≤m´ax{k, k0}. Así, del hecho de que pa a odo l, d0< l < d, se dé que
l6=d00, en onces es cla o que la clase ˆ
C0|dde inida en dicho lema es á en ˆ
Cn,w|d.
Teo ema 2.7.3 (Rep esen an e mínimo).Sea d≥0, y sea una clase ˆ
C|d+1 de mane a que k=
|Ed(ˆ
C)|. En onces exis e una clase ˆ
C0|0 al que ˆ
C0|d+1 =ˆ
C0|d+1 de mane a el índice de ˆ
C0|0sea
mínimo.
Demos ación. En es as condiciones, podemos ene dos si uaciones: que exis a un ni el l, d ≤l≤n,
al que |El(C)|=wo que no exis a dicho ni el.
Si exis e dicho ni el, en onces nos es igual cuán os inpu s oma o el núme o de pue as empleadas
en cada ni el siemp e que el ci cui o es é bien o mado (es deci , cumpla la p oposición 2.1.4 y no
enga un ni el con más de wpue as). Así, dado que σd(k)≤σd(k)y(ηd◦σd)(k)≤k, podemos
oma d0= 0, k0=σd(k)en el co ola io 2.7.2 pa a ob ene la mínima clase ˆ
C0|0, ya que no hay
meno alo de k0posible.
Si no, apliquemos el lema 2.1.7 pa a ob ene el mínimo l al que |Ed(C0)|=wpa a cualquie
ci cui o C0. Ya que l < d, podemos aplica el co ola io 2.7.2 con d=l,k=w,d0= 0 yk0=σl(w)
pa a ob ene una clase ˆ
C00|0 al que ˆ
C00|l=ˆ
C|l(y en consecuencia ˆ
C00|d=ˆ
C|d) de mane a que el
índice de ˆ
C00|0sea mínimo den o de ˆ
C|d. Aho a bien, ˆ
C00|0se puede ex ende a un ci cui o al y
como obse amos aquí. Con lo que podemos habla de C00 o de ˆ
C00|0casi indis in amen e (nos es
igual qué C00 ∈ˆ
C00|0 oma pa a con inua con la demos ación).
Po an o, apliquemos de nue o el co ola io 2.7.2 ía C00 con dykde inidos en las hipó esis y
d0=l,k0=w; ap o echando el hecho de que la desigualdad ηd−l(w)≤kse da en el ci cui o C.
Así, ob enemos una clase ˆ
C0|l al que ˆ
C000|d=ˆ
C00|d=ˆ
C|dde índice mínimo sob e ˆ
C|d. Así, sea
C000 un ci cui o de ˆ
C000|l. Apliquemos de nue o el mismo co ola io con C000,d=l, k =w, d0= 0
yk0=σl(w)pa a ob ene ˆ
C0|0de índice mínimo sob e ˆ
C000|l=ˆ
C|l(y en consecuencia de índice
mínimo sob e ˆ
C|d).
No emos inalmen e que po la demos ación del lema 2.7.1, pa a odo j al que 0≤j < l,
los ec o es jasociados al ni el j-ésimo de ˆ
C0|0coinciden con los ec o es jde ˆ
C00|0, con lo que
compu acionalmen e solo es necesa io aplica el co ola io dos eces.
El nomb e de es e eo ema cla amen e iene su o igen en la posibilidad de pa i de una clase
de Cn,w|dy ans o ma la en un ci cui o en Cn,w con mínimo índice.
Algo i mo 2.7.4 (Rep esen an e mínimo).Ob ención del mínimo ep esen an e de C|d
46

Algo i mo 5 Rep esen an e mínimo
Requi e: d,C, p
while d > 0do .Sub u ina ex ensión.
p← p[d]
k← [d−1]
C←Vec o mínimo
g←Tipo mínimo
C←C∪( , g)
d←d−1
end while
e u n C
Requi e: d,C|d
C←C|d
i Exis e j≥d al que |Ej(C)|=w hen .Caso 1del Rep esen an e mínimo
p←Ex ensión mínima . pcon iene a odos los kl.
else .Caso 2del Rep esen an e mínimo
l←Mínimo ni el
p1←Ex ensión mínima .Aplicado pa a ob ene C00.
p2←Ex ensión mínima .Aplicado pa a ob ene C000.
p← p2∪ p1
end i
C←Sub u ina ex ensión
e u n C
Po las obse aciones ealizadas en el algo i mo 2.5.10, es cla o que el cos e de es e algo i mo
es á en O(dp log(p)). Sin emba go, no emos que g acias a nues o eco ido en dos e apas ( ipos y
cableado), conseguimos e a da la ejecución de es e algo i mo den o del ni el d.
Ejemplo 2.7.5. Veamos de mane a p ác ica la aplicación del algo i mo 2.7.4 a la clase ˆ
C|3∈ C4,4
sob e m≥2inpu s siguien e:
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








Figu a 2.10: Ejecución del algo i mo 2.7.4 a pa i de ˆ
C|3.
En p ime luga , obse emos que ˆ
C|2no iene ningún ni el con 4pue as. Así, aplicando el lema
2.1.7 ob enemos que l= 2 y po el co ola io 2.7.2 ob enemos que k2= 3, k1= 4, k0= 2.
Así, el ec o mínimo cuando p= 3, k = 6 es h0 0 0 1 2 3i, el ec o mínimo cuando
p= 6, k = 2 es h0 0 0 1 0 1 1 1iy inalmen e, la mínima colección de 2inpu s es h0 1i

Aho a, y g acias a odos los lemas desa ollados podemos esponde algo undamen al: ¿cuál
es la p ime a clase que debemos oma ? Pa a ello, demos emos el siguien e eo ema de mane a
cons uc i a.
Teo ema 2.1.8. El conjun o Cn,w no es acío si y solo si dado d=dlog2(m´ax{2,logm(w)})e, se
da que ηn−d(w)=1.
Demos ación. Una de las implicaciones ya la demos amos en su momen o, así que es momen o de
comple a la p ueba. En p ime luga obse emos que exis e una co espondencia na u al en e los
ci cui os Cde p o undidad ny los ci cui os de p o undidad n+1 que son de la o ma C0:=id(C, C).
La idea de es a demos ación consis e en oma un elemen o a bi a io de Cny ob ene un elemen o
de Cn,w.
Dado que ηn−d(w)=1, ob enemos i ialmen e que ηn−d(w)≤1yσn−d(1) = 1 ≤w. Tomemos
48
ˆ
C|n+1 = (0,0). No emos que podemos eplica la demos ación de la segunda pa e del eo ema
2.7.3 pa a d=n, k = 1 u ilizando el lema 2.7.1 (sin ga an iza en ningún momen o que pe enece el
ci cui o a ˆ
Cn,w). Así, analizando la clase ob enida ˆ
C|0, obse amos que |El(C)|=wy que Ej(C)≤w
si j6=l, con lob enido ía el lema 2.1.7. Solo hemos enido que cambia la jus i icación de po qué
ηn−d(w)≤1pa a de mane a cons uc i a ob ene un elemen o de ˆ
Cn,w.
Finalmen e, g acias al co ola io 2.3.2 podemos ob ene un ep esen an e C00 ∈C00|n+1. Es e
elemen o es á en C|n,w, con lo que hemos acabado la demos ación.
Además, no emos que el ci cui o ob enido es el mínimo ci cui o según el índice y a es e ci cui o
lo denomina emos ci cui o inicial. Como e a de espe a , no podemos habla del caso base de un
algo i mo sin conoce su es uc u a. Po ello es su a día apa ición. Si epasamos con cuidado el
ejemplo 2.1.13, es cla o que es e ejemplo ep esen a el ci cui o inicial con los alo es m= 6, n =
4, w = 3. Además, en es e ejemplo se e bien la necesidad de pe mu a los inpu s, ya que es e
ci cui o u iliza solo 2de los 6que iene a su disposición.
Algo i mo 2.7.6 (Ci cui o inicial).Ob ención del ci cui o inicial.
Algo i mo 6 Ci cui o inicial
Requi e: n, w, m ∈Z, l =dlog2(m´ax{2,logm(w)})e, ηn−l(w)=1
C← ∅
C←Rep esen an e mínimo
e u n C
Demos ación. La co ección de es e algo i mo se sigue del eo ema 2.1.8. Además, su cos e es á en
O(nw log(w)), más solo se a a llama una única ez.
Ejemplo 2.7.7. Mos a emos, po comple i ud, un ejemplo de ci cui o inicial.








0 0
0 1
0 0 1 2
0 0 0 1 0 1
0 1








Figu a 2.11: Ejemplo de ci cui o inicial en C4,3con m≥2inpu s.

Esc ibamos, en a as de esumi es e capí ulo, el algo i mo en e o con el que eco e Cn,w.
Algo i mo 2.7.8 (El algo i mo del índice).Reco ido de Cn,w
49
Algo i mo 7 El algo i mo del índice
Requi e: n, w, m ∈Z, ηn−1(w)=1, m ≥σ(w)
C←Ci cui o inicial
L←[C]
σ←Mínima pe mu ación.
while Cno sea None do .Equi alen e a Fin del algo i mo.
i Exis e σ0> σ hen .Podemos cambia los inpu s.
C←(C σ)∪σ
σ←σ0
else
d←1
while d≤ndo
g0←Inc emen o del ipo
0←Inc emen o del cableado
i gno es None hen
C|d←(C|d g)∪g0
g←g0
b eak
else i no es None hen
g0←Tipo mínimo
C|d←(C|d ( , g)) ∪( , g0)
( , g)←( 0, g0)
b eak
else i Se cumple el eo ema Ampliación del suelo hen
0←Vec o mínimo
g0←Tipo mínimo
C|d←(C|d ( , g)) ∪( , g0)
( , g)←( 0, g0)
b eak
end i .else Tenemos que cambia de clase C|d+1
d←d+ 1
end while
i d=n+ 1 hen
C←None
else
C←Rep esen an e mínimo
end i
end i
L←L∪[C]
end while
50
núme o de pue as en un ni el epe cu e de mane a más di ec a en la endogamia del ni el in e io
que en el caso an e io . Además, enemos el siguien e lema:
Lema 3.3.9. Sea Cde p o undidad n. Si l∈N,0≤l < n, la endogamia en elazada en el ni el l
de Ces á en e 0y1.
Demos ación. Análoga al lema an e io .
En consecuencia y de mane a análoga, podemos habla del siguien e concep o.
De inición 3.3.10. Dado un ci cui o Cde p o undidad n, de inimos la endogamia mul ini el en-
elazada como la unción ec o ial ˆee(C)=(ee0(C), ..., een−1(C)).
Ejemplo 3.3.11. Mos emos aho a la endogamia mul ini el en elazada en el ejemplo 3.1.1. En
es e caso ee0≈0,2187,ee1= 0,1250,ee2≈0,2103 yee3= 0. Po an o, la endogamia ob enida es
ˆee(C) = (0,2187,0,1250,0,2103,0).
Es a de inición apa en emen e p opo ciona algo más de disc iminación, ya que dis ingue el ni el
3del ni el 1. Con ello, las clases de ci cui os ob enidos se án de un mayo espec o y se pod án
analiza con mayo de alle. Sin emba go, pudie a se que es a de inición es é excesi amen e ligada al
ci cui o y di icul e la clasi icación de los mismos según la unción que compu en, que es el obje i o
úl imo de es e capí ulo.
3.4. Endogamia po colapso
Sea Cun ci cui o de p o undidad ny sea ˆeun ec o de dimensión ncuyas componen es es án
no malizadas. Nues o obje i o en es a y las siguien es secciones se á busca combinaciones lineales
de las componen es de ˆede mane a que la de inición esul an e se compo e adecuadamen e según
nues os es ánda es.
De inición 3.4.1. Dado = ( 0, ..., n−1)∈Rndecimos que es un ec o de coe icien es si odas
sus componen es son no nega i as y n−1
P
i=0
i= 1.
De inición 3.4.2. Dado un ci cui o Cde p o undidad n, decimos que una unción ∈ C → [0,1]
es una endogamia po colapso ponde ado si exis e un ec o de coe icien es C∈Rn al que (C) =
C·ˆe(C).
In ui i amen e, el apellido po colapso de es a de inición se basa en que, al pasa un ci cui o de
su ep esen ación maximal a su ep esen ación minimal, a ias de las pue as han podido acaba
esul ando la misma, colapsando a un ep esen an e. Sin emba go, la ponde ación de es os colapsos
se deja al consumido y eso es lo que amos a a a de es udia .
Lema 3.4.3. Sea Cun ci cui o de p o undidad ny sea Cun ec o de coe icien es asociado a C.
En onces C·ˆe(C)∈[0,1].
57

Demos ación. Ya que C= ( 0C, ..., n−1C)cumple que odos sus coe icen es son meno es o iguales
que 1y dado que ˆeC= (e0(C), ..., en−1(C)) iene odas sus componen es meno es o iguales que 1,
enemos que C·ˆe=n−1
P
i=0
iC·ei(C)≤
n−1
P
i=0
iC= 1. Po o a pa e, al se an o Ccomo ˆe(C)no
nega i os, se cumple que C·ˆe(C)≥0.
3.4.1. Endogamia po colapso mínimo y máximo
Una p ime a idea se ía supone que las endogamias po ni el son independien es y que quizás
lo más sencillo sea coge el meno o el mayo alo de es os espec i amen e. Así, p oponemos las
siguien es de iniciones.
De inición 3.4.4. De inimos la endogamia po colapso mínimo como la unción ecmin ∈ C → [0,1],
de inida así: ecmin(C) = m´ın{el(C),0≤l < n}, donde nes la p o undidad del ci cui o C.
De inición 3.4.5. De inimos la endogamia po colapso máximo como la unción ecmax ∈ C → [0,1],
de inida así: ecmax(C) = m´ax {el(C),0≤l < n}, donde nes la p o undidad del ci cui o C.
Ambas de iniciones se pueden e como un caso pa icula de una endogamia po colapso pon-
de ado omando como ponde ación al ec o C= (∂1,k, .., ∂n−1,k), donde kes el meno índice al
que la endogamia de Cen dicho ni el es mínima ( espec i amen e, máxima) y ∂i,k es la del a de
K onecke .
Sin emba go, amos a analiza es as de iniciones b e emen e pa a e si son con enien es.
Lema 3.4.6. La endogamia po colapso mínimo de un ci cui o de p o undidad nsolo oma los
alo es 0ylog2n−2+1(2).
Demos ación. Sea Cun ci cui o de p o undidad n. En el ni el n−1hay una o dos pue as. Si
hubiese dos, en onces la endogamia de dicho ni el se ía 0ya que cada ci cui o de p o undidad
n−1solo pod ía apa ece una única ez. Si no, la endogamia de es e ni el se ía log2n−(n−1+1)+1(2)
y podemos p ocede de mane a induc i a, suponiendo que hemos p obado que ∀l, k < l ≤n, en
el ni el lhay exac amen e una pue a o bien exis e un ni el in e medio en el que la endogamia
es nula y con inuamos azonando como en el ni el n−1. En un núme o ini o de pasos hemos
ob enido que o bien en algún ni el se alcanza el alo 0, o ˆe= (1,log32, ..., log2n−2+1(2)). Po an o,
ecmin(C)∈ {0,log2n−2+1(2)}.
En de ini i a, es a de inición no apo a demasiado ya que disc imina de mane a muy g uesa la
di e sidad de ci cui os. Sin emba go, no podemos ealiza un análisis así sob e la endogamia po
colapso máximo, ya que en ci cui os no ex emos es os alo es oman alo es a bi a ios, pudiéndose
alcanza an o la co a mínima, 0, cuando el ci cui o es á en ep esen ación maximal has a la co a
máxima, 1, cuando el ci cui o iene únicamen e npue as. Po ello, es a úl ima puede se conside ado
como una mé ica azonable.
58
Ejemplo 3.4.7. Calculemos ápidamen e la endogamia po colapso mínimo y po colapso máximo
en el ejemplo 3.1.1. En es e caso, ecmin(C)=0yecmax(C)=0,4206.
Aún así, es as dos de iniciones gene an dudas en cuan o a si son capaces de ecoge oda la
exp esi idad que la de inición de ci cui o iene. Po ello, amos a p opone nue as de iniciones de
endogamia.
3.4.2. Endogamia po colapso di ec o
Una idea bas an e azonable es supone que no odos los ipos de ci cui os in luyen de la misma
mane a. Po ejemplo, si un ci cui o de p o undidad 1es u ilizado po un g an núme o de ci cui os
de p o undidad 2es cla o que el cambio de alo en su e aluación puede a ec a mucho más en el
esul ado inal. Es e puede no se debe oma como un axioma ni como una a iable p obabilís ica,
sino como la in uición que guia á es a de inición. Además, cuan o más aumen emos la p o undidad
de los ci cui os, un cambio en la e aluación de dicho ci cui o se p opaga á a p io i a menos ci cui os.
Po odo ello:
De inición 3.4.8. De inimos la endogamia po colapso di ec o como la unción ecd ∈ C → [0,1],
de inida así: ecd(C) = d·ˆe(C), donde d=1
1−2−n(2−1,2−2, ..., 2−n)ynes la p o undidad del
ci cui o C.
Es cla o que des un ec o de coe icien es ya que la suma de sus componen es es 1. Además,
e leja ielmen e lo explicado an e io men e.
3.4.3. Endogamia po colapso in e so
Sin emba go, podemos ealiza un azonamien o in e so al an e io : un cambio en la e aluación
de un ci cui o de p o undidades muy ele adas es más p obable que se e leje en un cambio eal en la
e aluación del ci cui o de mane a global. Po ello, quizás nos in e ese ponde a de mane a in e sa
a lo an e io , ocalizándonos en las endogamias supe io es y no las in e io es.
De inición 3.4.9. De inimos la endogamia po colapso in e so como la unción eci ∈ C → [0,1],
de inida así: ecd(C) = i·ˆe(C), donde i=1
1−2−n(2−n,2−(n−1), ..., 2−1)ynes la p o undidad del
ci cui o C.
Es además inmedia o po lo dicho an e io men e que ies un ec o de coe icien es. Nó ese
que en ambos casos se han omado coe icien es de la o ma 2−ksolamen e po el hecho de que su
ep esen ación maximal es un á bol equilib ado donde el núme o de pue as es siemp e po encia de
dos; pod íamos habe elegido o o ec o de coe icien es y habe azonado de mane a análoga con
es as dos de iniciones.
Ejemplo 3.4.10. La endogamia po colapso di ec o asociado al ejemplo 3.1.1 es ecd(C)≈0,3378
y la endogamia po colapso in e so esul a eci(C)≈0,1689. In ui i amen e es o quie e deci que
si es imamos que la causa de la endogamia es á en los ni eles supe io es, es e ci cui o no lo es, ya
59
que el p ime y el segundo ni el se expanden casi en su o alidad. Sin emba go, si nos ijamos en la
endogamia di ec a, iene más sen ido un “al o” alo ya que hay a la pos e pocos nodos. 
3.4.4. Endogamia po colapso en elazada
O a idea que puede se in e esan e es a a de medi la p opagación de mane a di ec a e
in e sa, pe o eniendo en cuen a la endogamia en elazada. Así, podemos ealiza un análogo al
caso an e io con es as de iniciones.
De inición 3.4.11. De inimos la endogamia po colapso di ec o en elazada como la unción
ecde :C → [0,1] de inida como: ecde(C) = d·ˆee(C), donde des el ec o de coe icien es de la
de inición 3.4.8.
De inición 3.4.12. De inimos la endogamia po colapso in e so en elazada como la unción
ecie :C → [0,1] de inida como: ecie(C) = i·ˆee(C), donde ies el ec o de coe icien es de la
de inición 3.4.9.
Finalmen e, a a emos de e ina la idea di ec a eniendo en cuen a, pa a cada ni el l, a cuán os
ci cui os del ni el l+ 1 pod ía a ec a en ealidad un cambio en la e aluación del ci cui o.
De inición 3.4.13. De inimos la endogamia po colapso bi-en elazado como la unción ecbe :C →
[0,1] de inida como: ecbe(C) = b(C)·ˆee(C), donde b(C) = 1
n
P
l=1
|El+1(C)|
(|E1(C)|, ..., |En(C)|)
Ejemplo 3.4.14. Calculemos pues las endogamias po colapso de inidas u ilizando las endoga-
mias en elazadas con el ya ecu en e ejemplo 3.1.1. Los alo es ob enidos son: ecde(C)≈0,1780,
ecie(C)≈0,0873 yecbe(C)≈0,1670.
Po una pa e, ob ene que ecde(C)> ecie(C)es lo espe ado al pode ealiza la misma a gu-
men ación que en el ejemplo an e io . Po o a pa e, po la na u aleza del ec o dy la del b(C),
los cuales ponde an el núme o de ci cui os a las que a ec a un cambio en un ni el, iene sen ido que
se dé que ecde(C)≈ecbe(C).
De es e ejemplo su ge una p egun a in e esan e: ¿in oduci el concep o de en elazamien o
gene a uido gene ando más clases de ci cui os o p opo ciona dis inción sin pe de la po encia de
la de inición de colapso di ec o?
3.5. Umb al de colapso
Una p egun a na u al de odas es as de iniciones es cómo a ía la endogamia po colapso de los
ci cui os en unción de los ec o es de coe icien es, o lo que es lo mismo, si exis e alguna mane a de
en ende cómo pode disc imina u ilizando es as endogamias y cómo a ec an es as modi icaciones.
De inición 3.5.1. Se denomina pe mu ación a cualquie unción biyec i a σ∈X→X.
60
Noso os oma emos usualmen e como X={1, ..., n}. Además, dado un ec o = ( 1, ..., n)en
Rny una pe mu ación σ, abusa emos de la no ación y habla emos del ec o σ( )=( σ(1), ..., σ(n)).
De inición 3.5.2. Sea λ= (λ1, ..., λn). Se denomina λ-umb al mínimo a la unción uλ∈ C → [0,1]
que minimiza σ(λ)·ˆe(C), con σpe mu ación.
De inición 3.5.3. Sea λ= (λ1, ..., λn). Se denomina λ-umb al máximo a la unción Uλ∈ C → [0,1]
que maximiza σ(λ)·ˆe(C), con σpe mu ación.
Teo ema 3.5.4 (Desigualdad de eo denamien o).Sean x1≤ ··· ≤ xnyy1≤ ··· ≤ yndos
colecciones de n alo es o denados. En onces x1yn+···+xny1≤x1yσ(1) +···+xnyσ(n)≤x1y1+
···+xnyn, donde σes una pe mu ación cualquie a. [4]
Co ola io 3.5.5. Dado λ ec o de coe icien es de amaño n, las unciones uλyUλse pueden
ob ene pa a cada ci cui o en iempo en O(nlog(n)).
Demos ación. De la desigualdad de eo denamien o ob enemos que nos bas a con o dena el ec o
λy el ec o ˆe(C)y mul iplica dichos ec o es o denados adecuadamen e. Y eso es cla o que se
puede ob ene en iempo O(nlog(n)).
De inición 3.5.6. Denominamos λ-umb al de colapso de un ci cui o al in e alo [uλ(C), Uλ(C)].
De odo lo explicado an e io men e nos damos cuen a de que las endogamias po colapso mínimo
y máximo no son sino pe mu aciones del ec o 0= (1,0, ..,0), al igual que lo son las endogamias
po colapso di ec o e indi ec o con λ= d. De hecho, ecmin =u 0yecmax =U 0.
Podemos da la uel a a es e concep o y e , ijado un ec o de coe icien es, cómo a ía la
endogamia en unción de la endogamia de cada ni el. Po ejemplo, en la endogamia po colapso
di ec o, no es lo mismo que los ni eles supe io es engan alo es al os de endogamia a que sean los
in e io es los de al a endogamia; en el p ime caso ob end íamos un alo de endogamia po colapso
di ec o mucho meno que en el segundo.
61
Capí ulo 4
G amá icas y ci cui os
En es e capí ulo e oma emos el es udio eó ico del espacio de ci cui os median e las unciones
booleanas que compu an, es deci , analizando e #(C), en a as de busca elaciones en e los ci cui os
y las unciones que compu an.
Reco demos que uno de los concep os que que íamos es udia es la elación en e la epe i i idad
en el pa ón de una unción y los ci cui os que compu an es as unciones. Sin emba go, es a idea pue-
de se obse ada de muchas mane as. Po ejemplo, la unción 00001111000011110000111100001111
se puede e como epe i cua o eces el pa ón 00001111 o epe i 01111000 es eces con p e ijo
000 y su ijo 01111. Sin emba go, nues a isión de la epe i i idad es a á basada en la bisección
ei e ada del pa ón, buscando una única mane a de exp esa es e enómeno que simpli ique, en ge-
ne al, la exp esión del mismo. Pa a ello, nos ald emos del concep o de g amá ica lib e de con ex o,
un mane a de consegui unciones booleanas de na u aleza muy dis in a a la abajada has a aho a
con los ci cui os, pe o que sin emba go no son del odo ajenas la una de la o a.
4.1. G amá icas lib es de con ex o
Reco demos en p ime luga el concep o de g amá ica lib e de con ex o.
De inición 4.1.1. Denominamos g áma ica lib e de con ex o a la upla G= (V,Σ,P, S)donde:
Ves el conjun o de a iables,
Σes el conjun o de e minales,
Pes el conjun o de p oducciones,
Ses la a iable inicial.
La p incipal aplicación de es as g amá icas iene ecogida en el siguien e esul ado:
62

Teo ema 4.1.2. Todo elemen o de F22nse puede ob ene median e una g amá ica lib e de con-
ex o con Σ = {0,1}y un conjun o de a iables y p oducciones i edundan es, es deci , conjun os
cuyos elemen os son dis in os dos a dos.
Demos ación. La demos ación de es e eo ema se á cons uc i a e induc i a. En p ime luga ,
pa ece azonable oma dicho conjun o de e minales ya que los elemen os de F2son {0,1}. Además,
deno a emos in ( ), ∈F22nal núme o ˜
(2), donde ˜
es el polinomio en Z[x]cuyos coe icien es
son = ( 0, . . . , 2n)(de mane a que los elemen os 0y1de F2se co espondan con el 0y el 1de
Z).
Sea n= 0. En onces = 0 o = 1 y de inamos P0,in ( )=V0,in ( )→ . Así, omemos
V={V0,in ( )},P={P0,in ( )}yS=P0,in ( ). Es inmedia o obse a que es a g amá ica gene a
y que sa si ace las hipó esis del eo ema.
Así, azonemos po inducción, supues o que odo elemen o de F2n
2es gene able po una g a-
má ica como en el enunciado. Dado ∈F2n+1
2, es una 2n+1- upla de elemen os de F2, con lo
que deno a emos po 1= ( 2n+1−1, ..., 2n)y 2= ( 2n−1, ..., 0), de mane a que con = 1· 2
deno a emos la conca enación de uplas, no el p oduc o. Po hipó esis de inducción, exis en dos
g amá icas G1= (V1,Σ,P1, S1)yG2= (V2,Σ,P2, S2)de mane a que gene an 1y 2 espec i-
amen e. Po an o, de inamos Pn+1,in ( )=Vn+1,in ( )→Vn,in ( 1)·Vn,in ( 2)y obse emos que
deno ando P=P1∪P2∪{Pn+1,in ( )},V=V1∪V2∪{Vn+1,in ( )}yS=Pn+1,in ( ), ob enemos
que G= (V,Σ,P, S)es una g amá ica lib e de con ex o que gene a y se cumple que VyPson
i edundan es g acias a la no ación aplicada en a iables y p oducciones (jun o a la de inición de
conjun o, que no pe mi e mul iplicidad).
Ejemplo 4.1.3. Sea n= 3 y = 00011010. Así, el conjun o de p oducciones que gene an dicha
unció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 cu si a hemos indicado pa a cada p oducción Pn,k qué unción de amaño 2ngene a.
Pa a inaliza la sección, ya que hay una in e dependencia en e a iables y p oducciones, e-
ma ca emos que ealiza emos un abuso del lenguaje, ya que habla emos indis in amen e de ambos
concep os en a as de hace más li iana la siguien e sección.
4.2. Ope ado es no simé icos y el eo ema de equi alencia
Nues o obje i o, como buenos ma emá icos, consis i á en educi el es udio de las g amá icas al
caso an e io de los ci cui os, pa a ap o echa sus nociones y cons ucciones. Pa a ello, obse emos
63
que las g amá icas expues as en el eo ema 4.1.2 iene una apa iencia de ci cui os. Sin emba go, no
es an sencillo comno se que ía.
De inición 4.2.1. Di emos que un ope ado P∈ C × C → C0es no simé ico si no es simé ico
pa a odo C1, C2∈ C, C16=C2.
Aunque es a de inición pa ece innecesa ia, nos si e pa a pone el oco en lo siguien e: Vse
puede cons ui de mane a idén ica a Ccon un poco más de es ue zo.
De inición 4.2.2. Deno a emos po Vnal conjun o de a iables Vn,k empleables po la g amá ica
de inida en el eo ema 4.1.2 pa a gene a el elemen o ∈F22n, donde k=in ( ).
Lema 4.2.3. El conjun o Vn iene 22nelemen os.
Demos ación. Es inmedia o debido a que Vnes á en biyección con F22n.
De inición 4.2.4. Deno a emos po e #0:V0→F2al ope ado e aluación: e #0(V0,k) = k.
De inición 4.2.5. Deno a emos po e #n:Vn→F22nal ope ado e aluación e #n(Vn,k) =
xn·e #n−1(Vn−1,k1) + e #n−1(Vn−1,k2). Además deno a emos po E #aE #={e #n, n ∈N}.
Así, obse a emos que podemos de ini la siguien e pue a lógica:
De inición 4.2.6. Deno a emos po ·∈Vn× Vn→ Vn+1 a la pue a lógica conca enación, de
mane a que el equi alen e de dicha pue a sea eq(·)∈F22n×F22n→F22n+1 de inido así: eq(·)( , g) =
eq(·)(( 2n−1, . . . , 0),(g2n−1, . . . , g0)) = ( 2n−1, . . . , 0, g2n−1, . . . , g0), de mane a que se cumple que
(e #n+1 ◦·) (V, V 0) = eq(·)(e #n(V), e #n(V0)).
Como se puede e , g acias a la lexibilidad de la de inición asociada al ope ado e aluación,
podemos de una mane a muy cómoda habla de la pue a lógica conca enación y en consecuencia
e el espacio de a iables Vcomo un espacio de ci cui os cons uidos con el ope ado ·. Sin emba go,
es a cons ucción di ie e de la usual an o en el núme o de ope ado es como en el ipo de pue a, al se
cla o que la conca enación no es simé ica. Po ello, un obje i o azonable se ía busca una mane a
de ans o ma Ven Cpa a pode u iliza odas las he amien as mencionadas an e io men e. En
conc e o, eniendo en men e el obje i o del expe imen o, de log a es a ans o mación pod emos
ap o echa nos del algo i mo 2.7.8 pa a eco e de mane a exhaus i a V.
Teo ema 4.2.7 (Teo ema de equi alencia).Todo elemen o de Ves á en co espondencia con uno
de Cen ep esen ación minimal y bien conec ado cuando m= 2. Además, se puede log a es a
biyección compa ible con el índice en C.
Demos ación. En p ime luga , po el lema 4.2.3 y el co ola io 1.3.3, es cla o que pa a odo n∈Nse
da que |Vn|=|Cn|= 22n<∞, con lo que de una mane a c is alina obse amos que dicha biyección
exis e y en consecuencia, el g ueso del eo ema queda ya p obado. Sin emba go, mos a emos cómo,
de odas las biyecciones exis en es, elegi una biyección φcompa ible con el índice.
Si n= 0, podemos oma φ(in0) = V0,0yφ(in1) = V0,1. Así, V0≈ C0y podemos habla de la
unción índice 0sob e V0. Apliquemos aho a inducción sob e n, de mane a que Vn≈ Cny podamos
64
habla de nsob e Vn. En ese caso, dado C0:=P(C1, C2)de p o undidad n+ 1, pueden da se es
casos:
P=id. En es e caso C1=C2y en consecuencia, sus índices coinciden. Así, deno ando k=
2n n(C1) + n(C2), podemos de ini φ(C0) = Vn+1,k.
P=∨. En es e caso n(C1)< n(C2)po la buena conexión de C0. Así, deno ando a bi a-
iamen e k= 2n n(C1) + n(C2), podemos de ini φ(C0) = Vn+1,k.
P=∧. En es e caso ambién se da que n(C1)< n(C2). Así, deno a emos k= 2n n(C2) +
n(C1), y de ini emos φ(C0) = Vn+1,k.
Es a aplicación es cla amen e biyec i a y espe a el índice en el sen ido siguien e: dados V1, V2, V3∈
Vn ales que V1≤V2≤V3, V16=V3, se da que V1V2≤V2V1< V1V3< V3V1(donde la p ime a
desigualdad es una igualdad si V1=V2). Es o es impo an e po que es a desigualdad hace co es-
ponde a Vuna unción índice que o malmen e se de ine de mane a análoga a la de Cy, lo que es
más impo an e, nos pe mi e eco e Vcon el algo i mo 2.7.8 de una mane a na u al: solo hay que
in e p e a el ci cui o ob enido como una a iable.
El eo ema 4.2.7 se puede enuncia así: en un espacio Ccon un o den o al odo ope ado no
simé ico P:C×C → C0se co esponde con dos ope ado es simé icos P1, P2:C×C → C0 ales que
pa a odo C∈ C, P1(C, C) = P2(C, C). Sin emba go, hemos decidido expone lo con un enunciado
más simpli icado pa a e su aplicación inmedia a, aunque ello implique que se di umine la idea de
equi alencia implíci a en su apellido. Además, g acias a la biyección cons uida en dicho eo ema,
los concep os de endogamia expues os en el capí ulo 3no solo se pueden aplica , sino que iene
sen ido es udia los, ya que es uc u almen e es lo mismo un ci cui o que una p oducción.
Po odo ello su gen a ias p egun as que no pudimos ealiza en dicho capí ulo al no habe
hablado de es os concep os: ¿hay alguna elación en e la endogamia de un ci cui o que compu a
una unción y la p oducción que gene a dicha unción? ¿la g amá ica de una unción de e mina el
mínimo núme o de pue as de un ci cui o que compu e la misma?
65
Capí ulo 5
Resul ados y conclusiones
Finaliza emos el abajo ecapi ulando el expe imen o ealizado, exponiendo los esul ados ob-
enidos y ex ayendo alguna conclusión de los mismos.
Como ya se mencionó en la in oducción, el expe imen o ha consis ido en el eco ido exhaus-
i o del espacio de ci cui os, donde pa a cada ci cui o gene ado se ha ob enido la unción que es e
compu a y se ac ualiza una abla dispe sa en la que ano amos pa a cada unción el meno ci cui o
que la compu a. Además, se ha eco ido de igual mane a el espacio de las g amá icas asociadas
a unciones de 5bi s, pa a inalmen e a a odos los da os ob enidos de mane a es adís ica es u-
diando dis in as co elaciones en e a iables alea o ias basadas en los concep os de endogamia y el
núme o de pue as del ci cui o / eglas de la g amá ica.
5.1. Implemen ación del algo i mo del índice
Pa a pode ealiza nues o expe imen o, hemos ealizado una implemen ación del algo i mo
2.7.8 en C++ [5]. Po cla idad del código, se decidió sepa a en dos secciones de código di e en-
ciadas la gene ación de ci cui os de la e aluación de los mismos. Así, se ep esen ó cada ci cui o
en su ep esen ación ma icial compac a y el ci cui o en su ep esen ación ísica, como un á bol de
pun e os compa idos [6].
La necesidad de con a con ambas de iniciones iene la siguien e mo i ación: el algo i mo del
índice abaja con ma ices, mas la e aluación de un ci cui o nace con es a exp esión. Del paso
de una exp esión a la o a su ge la necesidad de abaja con la exp esión ma icial compac a,
una exp esión in e media en e ambas ep esen aciones; y pa a palia los p oblemas que su gen de
mane a inhe en e a la implemen ación de un á bol de pun e os, se ha u ilizado la lib e ía [7] pa a
de ec a ugas de memo ia.
Sin emba go, como se io en el co ola io 1.3.3, el núme o de ci cui os de mbi s c ece de mane a
doblemen e exponencial con la p o undidad; po lo que aun es ingiendo wel iempo de ejecución
66
ce cana a dicho alo .
Sin emba go, la posible exis encia de co elación en e el es o de endogamias es muy di usa, y
muy ligada al ipo de ci cui o in oluc ado. Nó ese que el conjun o de ci cui os mínimos con el que se
abaja es de mayo ca dinalidad que el es o de los ipos de los ci cui os. Po ello, conside amos una
mues a su icien emen e ep esen a i a de la co elación en e endogamias el caso de las g amá icas,
ya que la di e sidad es uc u al de ci cui os es mayo : los ci cui os mínimos ienden a ene baja
p o undidad y anchu a po la p opia de inición de los mismos, pe o sin emba go, las g amá icas
son ci cui os es uc u almen e a iados, con un amplio ango de núme o de pue as empleadas po
las mismas. Es a a i mación no se debe in e p e a como algo basado en un es udio en p o undidad
de la densidad de ci cui os y su ipo de endogamias en el subconjun o analizado, sino como una
azonable e in ui i a ap oximación basada en la p esunción de dis ibución equiespaciada de las
g amá icas que gene an unciones compu adas po algún ci cui o mínimo.
Po úl imo, des aca la nula co elación en e endogamias y unciones booleanas, lo cual e a algo
desg aciadamen e espe able.
5.6. Co elación en e las endogamias y núme o de pue as
empleadas
Po o a pa e, una p egun a azonable es e cuál de es as endogamias e leja mejo el núme o
de pue as empleadas. Pa a ello, dada la a iable alea o ia Easociada a la endogamia de un ci cui o
y la a iable alea o ia Gasociada al núme o de pue as, es udia emos si hay una co elación en e
EyG(caso Endogamia-Pue as), si la hay en e 1−EyG(caso Endogamia opues a - Pue as) o
si exis e dicha co elación en e 1
EyG(caso Endogamia in e sa - Pue as).
73

End.
ep esen aci´on
End. colapso
m´aximo
End. colapso
m´ınimo
End. colapso
di ec o
End. colapso
in e so
End. colapso
bien elazado
End. colapso
en elazado
di ec o End. colapso
en elazado
in e so
Endogamia -
Pue as
Op. endogamia -
Pue as
In . endogamia
- Pue as
Co elaciones endogamias s pue as - Ci cui o m´ınimo
−1.00
−0.75
−0.50
−0.25
0.00
0.25
0.50
0.75
1.00
Figu a 5.8: Ci cui os mínimos. Amplia
End.
ep esen aci´on
End. colapso
m´aximo
End. colapso
m´ınimo
End. colapso
di ec o
End. colapso
in e so
End. colapso
bien elazado
End. colapso
en elazado
di ec o End. colapso
en elazado
in e so
Endogamia -
Pue as
Op. endogamia -
Pue as
In . endogamia
- Pue as
Co elaciones endogamias s pue as - G am´a icas
−1.00
−0.75
−0.50
−0.25
0.00
0.25
0.50
0.75
1.00
Figu a 5.9: G amá icas. Amplia
End.
ep esen aci´on
End. colapso
m´aximo
End. colapso
m´ınimo
End. colapso
di ec o
End. colapso
in e so
End. colapso
bien elazado
End. colapso
en elazado
di ec o End. colapso
en elazado
in e so
Endogamia -
Pue as
Op. endogamia -
Pue as
In . endogamia
- Pue as
Co elaciones endogamias s pue as - Romboides
−1.00
−0.75
−0.50
−0.25
0.00
0.25
0.50
0.75
1.00
Figu a 5.10: Ci cui os con o ma omboidal.
Amplia
End.
ep esen aci´on
End. colapso
m´aximo
End. colapso
m´ınimo
End. colapso
di ec o
End. colapso
in e so
End. colapso
bien elazado
End. colapso
en elazado
di ec o End. colapso
en elazado
in e so
Endogamia -
Pue as
Op. endogamia -
Pue as
In . endogamia
- Pue as
Co elaciones endogamias s pue as - 4-Romboides
−1.00
−0.75
−0.50
−0.25
0.00
0.25
0.50
0.75
1.00
Figu a 5.11: Ci cui os con o ma 4- omboidal.
Amplia
En p ime luga , obse emos, como e a de espe a , que la endogamia po colapso mínimo no
ayuda a es udia los ci cui os ya que, en gene al, es idén icamen e nula. Así, omi iendo en lo que
sigue dicha mé ica, p osigamos el análisis. Como se puede obse a , en los ci cui os mínimos hay
una co elación posi i a en el segundo caso (endogamia opues a s núme o de pue as) y una
74
co elación nega i a en el p ime o (endogamia s núme o de pue as) independien emen e del ipo
de endogamia. Es o nos lle a a pensa (en con aposición a lo que sucede con las siguien es g á icas)
que dado un conjun o de ci cui os, un posible es de alidación sob e si es os son mínimos o no
se ía calcula las co elaciones plan eadas y obse a si dicho conjun o se compo a como en la
g á ica expues a.
Po o a pa e, en el caso de las g amá icas ob enemos que la endogamia po colapso en elazado
di ec o no co elaciona con el núme o de eglas que es a emplea. Además, la endogamia po colapso
di ec o co elaciona de mane a opues a a como lo hacía en el caso de los ci cui os mínimos.
En el e ce caso, obse amos que los ci cui os omboidales ambién se compo an de mane a
dis in a a los ci cui os mínimos: la endogamia po ep esen ación, colapso in e so y colapso en e-
lazado in e so se compo an a la in e sa que en el caso mínimo. Y inalmen e, el caso 4- omboidal
nos hace e algo oda ía más in e esan e: no nos son ú iles las endogamias po colapso máximo,
colapso in e so y colapso en elazado in e so; y de las que nos son ú iles, la endogamia po colapso
di ec o y colapso en elazado di ec o co elacionan de mane a opues a al caso mínimo.
Es o iene su explicación: los ci cui os omboidales se han elegido ad hoc con al a endogamia
en sus ni eles in e io es y baja endogamia en sus ni eles supe io es, y los 4- omboidales no ienen
endogamia alguna siquie a en los 3ni eles supe io es, lo que conduce a un compo amien o inú il
de las endogamias in e sas y un compo amien o anómalo de las endogamias di ec as.
Sin emba go, en es a e ahíla de di e encias en e un caso y o o nos damos cuen a de un
hecho: la endogamia po colapso bien elazada siemp e se compo a de una mane a semejan e. Es e
hecho pone de mani ies o la idea in ui i a que yacía sob e la de inición de dicha endogamia: en un
ci cui o, odo depende de las conexiones eales, no del ni el en el que nos encon emos. Po ello,
pa ece azonable a i ma que, de odas las endogamias, la que e leja mejo el núme o de pue as
empleadas es es a.
5.7. Co elación en e dis in os da ase s
Una ez hecho el análisis an e io , a emos de in en a halla algún ipo de elación en e las
endogamias, los ci cui os y las unciones que compu an pa a dis in os ipos de ci cui os. De nue o,
a a emos de es udia la co elación en e dis in as a iables alea o ias. En es e caso, y de iniendo
EyGcomo en el apa ado an e io , se ha op ado po :
1. Reu ilización simple: es udia la co elación en e las a iables X= (1 −E1)·G1,Y=
(1 −E2)·G2.
2. Reu ilización compleja: es udia la co elación en e las a iables X=G1,Y= (1 −E2)·G2.
3. Cocien e: es udia la co elación en e las a iables X=E1·G2,Y=E2·G1.
4. Cocien e opues o: es udia la co elación en e las a iables X= (1−E1)·G2,Y= (1−E2)·G1.
In ui i amen e en el p ime caso a amos de compa a el núme o de pue as empleadas en un
ipo de ci cui os y su exogamia (el alo 1−E) con el mismo alo en o o ipo de ci cui os, de
mane a que algún ipo de co elación di ec a nos quie a deci que a mayo núme o de pue as meno
alo de exogamia, y po an o, meno alo de endogamia.
75
La segunda si uación es pa ecida, pe o desp eciando el é mino de exogamia en dicha de inición.
La mo i ación de dicha decisión es aplica dicho análisis a ci cui os mínimos, donde la endogamia
ob enida se á, idealmen e, la meno posible.
En el e ce caso, a amos de busca co elación en e E1
E2yG1
G2. Sin emba go, po cues iones
écnicas de p ecisión se ha op ado po es a ans o mación aún sin se equi alen e. Es deci , los
esul ados de es e análisis no son di ec amen e ex apolables a la ans o mación (E1
E2,G1
G2), pe o
igualmen e se ha decidido lle a a cabo. Finalmen e, el úl imo análisis se jus i ica de la misma
mane a.
Reco demos, an es de p esen a el análisis, que se ha decidido pa a los conjun os de ci cui os
con o ma omboidal y 4- omboidal que se oma á, como ep esen an e de la clase de ci cui os que
compu an la misma unción, al ci cui o de meno endogamia.
End.
ep esen aci´on
End. colapso
m´aximo
End. colapso
m´ınimo
End. colapso
di ec o
End. colapso
in e so
End. colapso
bien elazado
End. colapso
en elazado
di ec o End. colapso
en elazado
in e so
Reu ilizaci´on
simple
Reu ilizaci´on
compleja
Cocien e
Op. cocien e
Co elaciones compa a i as - Ci cui o m´ınimo s Romboides
−1.00
−0.75
−0.50
−0.25
0.00
0.25
0.50
0.75
1.00
Figu a 5.12: Ci cui os mínimos en e a ci cui-
os con o ma omboidal. Amplia
End.
ep esen aci´on
End. colapso
m´aximo
End. colapso
m´ınimo
End. colapso
di ec o
End. colapso
in e so
End. colapso
bien elazado
End. colapso
en elazado
di ec o End. colapso
en elazado
in e so
Reu ilizaci´on
simple
Reu ilizaci´on
compleja
Cocien e
Op. cocien e
Co elaciones compa a i as - Ci cui o m´ınimo s 4-Romboides
−1.00
−0.75
−0.50
−0.25
0.00
0.25
0.50
0.75
1.00
Figu a 5.13: Ci cui os mínimos en e a ci cui-
os con o ma 4- omboidal. Amplia
Como se puede e , en ninguno de los dos casos ob enemos algún ipo de elación en e el núme o
de pue as empleado y su endogamia, lo que nos lle a a pensa que es e análisis no nos pe mi e
di e encia dos da ase s con ci cui os dis in os ni ayuda en el es udio de las unciones que es os
compu an. Finalmen e, se decidió ealiza el mismo análisis con on ando los ci cui os mínimos con
la g amá ica asociada a es os.
76
End.
ep esen aci´on
End. colapso
m´aximo
End. colapso
m´ınimo
End. colapso
di ec o
End. colapso
in e so
End. colapso
bien elazado
End. colapso
en elazado
di ec o End. colapso
en elazado
in e so
Reu ilizaci´on
simple
Reu ilizaci´on
compleja
Cocien e
Op. cocien e
Co elaciones compa a i as - Ci cui o m´ınimo s G am´a icas
−1.00
−0.75
−0.50
−0.25
0.00
0.25
0.50
0.75
1.00
Figu a 5.14: Ci cui os mínimos en e a g amá icas. Amplia
En es e caso pa ece habe algún ipo de elación en los dos úl imos análisis, po lo que pa ece
azonable es udia compa a i amen e las g amá icas en e a o os ipos de ci cui os.
End.
ep esen aci´on
End. colapso
m´aximo
End. colapso
m´ınimo
End. colapso
di ec o
End. colapso
in e so
End. colapso
bien elazado
End. colapso
en elazado
di ec o End. colapso
en elazado
in e so
Reu ilizaci´on
simple
Reu ilizaci´on
compleja
Cocien e
Op. cocien e
Co elaciones compa a i as - G am´a icas s Romboides
−1.00
−0.75
−0.50
−0.25
0.00
0.25
0.50
0.75
1.00
Figu a 5.15: G amá icas en e a ci cui os con
o ma omboidal. Amplia
End.
ep esen aci´on
End. colapso
m´aximo
End. colapso
m´ınimo
End. colapso
di ec o
End. colapso
in e so
End. colapso
bien elazado
End. colapso
en elazado
di ec o End. colapso
en elazado
in e so
Reu ilizaci´on
simple
Reu ilizaci´on
compleja
Cocien e
Op. cocien e
Co elaciones compa a i as - G am´a icas s 4-Romboides
−1.00
−0.75
−0.50
−0.25
0.00
0.25
0.50
0.75
1.00
Figu a 5.16: G amá icas en e a ci cui os con
o ma 4- omboidal. Amplia
Como se puede obse a , uno de los in a ian es que se p ese a en es as es úl imas g á icas es
una co elación in e sa en e las a iables X, Y en el caso cocien e pa a la endogamia po colapso
bien elazado. Jun o con la obse ación de la sección 5.6, en la cual azonábamos que exis ía una
co elación en e el núme o de pue as y dicha endogamia, es o pa ece indica que hay una co e-
lación exis en e en e el núme o de eglas de la g amá ica y el núme o de pue as que u iliza un
ci cui o ía la ans o mación de las a iables alea o ias ealizadas en es e caso.
77
Es a p opiedad nos puede se i pa a pode es ablece un posible umb al de minimalidad: en
unción del núme o de eglas empleadas po la g amá ica que compu e una unción booleana y
la endogamia de la misma, podemos es ablece unas es icciones necesa ias sob e la endogamia
po colapso bien elazada de cualquie ci cui o que compu e dicha unción. En onces, es udiando
dicha endogamia en p o undidad quizás podamos es ablece condiciones necesa ias pa a es ima el
mínimo amaño que debe ene un ci cui o que compu e dicha unción.
En cualquie caso, el di e en e compo amien o que es a compa a i a iene al en en a dos
ci cui os en e sí en e a en en a ci cui os y sus g amá icas, nos da que pensa que quizás, y
solamen e di emos quizás, nos hallemos an e un nue o e in e esan e camino de in es igación.
78

Conclusiones
Finaliza emos es e abajo con un b e e esumen de odo lo ob enido a lo la go de es e do-
cumen o, y explica emos una se ie de p oyec os pendien es que pod ían su gi como con inuación
na u al de es e expe imen o.
En p ime luga , eco demos que el obje i o de es e expe imen o e a ecaba e idencia empí ica
de la endogamia de los ci cui os y es udia la elación de es a endogamia con la unción compu ada
po es os.
Pa a ello, hemos desa ollado un o malismo ma emá ico muy lexible pa a de ini los ci cui os.
Es e o malismo nos ha pe mi ido de una mane a cómoda cambia el pun o de is a en e ci cui os
y g amá icas allá donde lo hemos necesi ado sin mucho es ue zo, g acias al eo ema de equi alencia.
Es o nos conduce a la in e esan e p opiedad de que oda la eo ía desa ollada pa a es udia las
g amá icas se puede adap a de alguna mane a pa a es udia los ci cui os booleanos. Po o a
pa e, hemos p obado que podemos encon a ep esen an es únicos de nues os ci cui os y do a
al conjun o de los mismos de un o den o al g acias a la ep esen ación minimal y a la unción
índice. Es a unción índice nos ha se ido pa a desa olla y demos a un complejo pe o a la ez
simple algo i mo con el que eco e el espacio de ci cui os. Complejo po la labo iosidad del mismo
y simple po la sencillez de los a gumen os empleados en su demos ación, los cuales no equie en
de as os conocimien os ni de ma emá icas ni de in o má ica.
Sin emba go, la implemen ación y el desa ollo del mismo han sido pa icula men e us an es
po el iempo in e ido en p og ama lo, es a lo y p oba odos los esul ados que nos conducen
a él; lemas esul an es del es udio bajo p ueba y e o de las condiciones necesa ias pa a eco e
odos los ci cui os. O o obs áculo encon ado en dicho algo i mo ha esidido en la inmensidad del
espacio es udiado, el cual compu acionalmen e e a inaba cable pa a el po a il con el que se ha
abajado. Es a inmensidad se e lejó no sólo a la ho a de eco e el espacio, sino a la ho a de
p ocesa los da os que en su eco ido ob eníamos: odas las decisiones de es ingi el conjun o
de da os sob e el que analiza nues os da os (como en el caso de los ci cui os omboidales o los
4- omboidales) han sido po la imposibilidad de p ocesa al can idad de in o mación.
A mayo es, y pa a pode u iliza los da os ecabados, hemos de inido una se ie de mé icas de
endogamia y el concep o de λ-umb al con el obje i o de encon a algún ipo de elación en e los
ci cui os y las unciones booleanas. Es os concep os a p io i pa ecían p ome edo es ya que conden-
saban de mane a adecuada la es uc u a de un ci cui o en un alo numé ico. Sin emba go, como
se ha is o en el capí ulo 5, los esul ados han sido un poco in uc uosos: en gene al, en e muchas
de las mé icas exis e una co elación y en múl iples ocasiones es o e a lo p e isible debido a las si-
79
mili udes inhe en es en la de inición. Y aquellas co elaciones no p e is as, aún siendo in e esan es,
des acan po su escasez. Además, los dis in os análisis plan eados no han ga an izado ningún ipo
de ce idumb e, sólo me as sospechas.
Po o a pa e, se ab e de mane a insospechada un posible camino de es udio: el es udio de
la co elación ía endogamia po colapso bien elazado en e g amá icas y ci cui os; algo que no
espe ábamos encon a pe o que des aca de mane a no able en e al es o de esul ados.
Po o o lado, si echamos la is a a ás y nos ijamos en el concep o de g a o and-in e so
in oducido en las p ime as páginas de es e abajo, obse amos que una implemen ación de ci cui o
u ilizando es e pa ón nos ga an iza una mayo e iciencia. En ez de eque i 2minpu s pa a
cons ui nues os ci cui os, exigimos abaja con 4pue as de dos inpu s y 2pue as de solo un
inpu . Así, el ca dinal de Cnes 2n·m2n, el cual, con on ado a los (2m)2nci cui os gene ados con
nues a de inición, conlle a una mejo a de 22n−n∈ O(22n).
De hecho, se puede comp oba que an o la unción índice como el algo i mo del índice pe ma-
necen p ác icamen e impasibles a es a decisión: odos los lemas son ácilmen e adap ables a es a
implemen ación. De hace se así, la can idad de ci cui os edundan es ob enidos se educe d ás i-
camen e, con lo que se pod ían ob ene mayo can idad de da os con los que alida o e u a las
conje u as p opues as.
Po úl imo, des aquemos que aunque pa ezca in uc uoso lo log ado con es e expe imen o, no
es así: en el p oceso de es udia es e espacio se han ob enido esul ados in e esan es y se plan ean
nue as ías de es udio con ue e ca ga ma emá ica e in o má ica que a p io i son un poco an i-
in ui i as. Más aún, se ha is o cómo es el p oceso de in es igación desde su ace a más di ec a y
más since a, y eso no se ap ende en un lib o.
80
Conclusions
This chap e will b ie ly summa ize all he esul s ob ained du ing ou expe imen , and i will
also include a discussion o he sui abili y o some u u e de elopable p ojec s om his wo k.
Fi s o all, le us no o ge ha he objec i e o his expe imen was o collec empi ic e idence
abou he endogamy o he boolean ci cui s and s udying he ela ion be ween he endogamy and
he boolean unc ions hey compu e.
Fo his pu pose, we ha e de eloped a ma hema ical o malism o de ine ou ci cui s. This
o malism has allowed us o exchange ci cui s and g amma s whe e e i was needed hanks o he
equi alence heo em. Tha leads us o hink ha e e y heo y in ol ing g amma s can be adap ed
o s udying boolean ci cui s. Mo eo e , we ha e ound a unique desc ip ion o ou ci cui s, hei
minimal ep esen a ion. No only i has been de ined a o al o de on he se o ci cui s, bu also an
index unc ion which has enabled us o de elop and p o e a complex, ye simple, sweeping algo i hm
o he se o boolean ci cui s.
Ne e heless, he ime-expensi e implemen a ion o his algo i hm has ca ied some us a ion,
due o es ing and p o ing i s co ec ion. In addi ion, o he obs acle ound in ou algo i hm was
he immense space s udied, unmanageable o he used lap op. This immensi y e lec ed bo h on
sweeping he ci cui s’ space and p ocessing all he da a collec ed: e e y da ase s educ ion is owed
o his eason.
Addi ionally, we ha e de ined some endogamy me ics and he concep o λ- h eshold in o de
o ind any kind o ela ion be ween boolean ci cui s and he unc ions hey compu e. Be o ehand,
hese de ini ions seemed p omising because hey summa ized adequa ely he s uc u e o a ci cui
in a nume ic alue. Ne e heless, as we ha e seen in Chap e 5, he esul s ob ained we e a bi
ui less: be ween many me ics he e exis s a i ial co ela ion, and he analysis o he da a does
no gi e a clea answe o he endogamy p oblem. Acciden ally we ha e ob ained a new esea ch
pa h: he s udy o he co ela ion be ween g amma s and ci cui s by using he biin e wined collapse
endogamy. This is some hing we did no expec o ind, bu we a e de ini ely glad o ha e done so.
Fu he mo e, e u ning he ocus o he and-in e e g aph men ioned in he in oduc ion o his
wo k, we ealize ha an implemen a ion o a ci cui using his pa e n shows a be e e iciency:
ins ead o using 2minpu s, we need o use wice di e en ga es as we use now. Doing so, he
ca dinali y o Cis 2nm2nins ead o (2m)2n, so he gain esul ing is 22n−n∈ O(22n). In ac , i can
be p o en ha bo h he index unc ion and he index algo i hm emain almos iden ical a e his
change in he implemen a ion. In his way i may be possible o ob ain mo e i edundan da a o
81
alida e o e use ou conjec u es.
Finally, we wan o ema k ha he g ea achie emen o his p ojec is he pa h ollowed in
i s p ocess. We ha e opened a pa h which is likely o be enhanced, a pa h whe e ma hema ics and
compu e science in e wine. Th ough he p ocess we ha e acqui ed in es iga ion skills ung aspable
wi h only he heo e ical con en o a book. To end up, we would like o highligh he impo ance
o he esul s no only o hemsel es bu o he wide knowledge and in es iga ion oppo uni ies
ha ha e been b ough up.
82
0 1 2 3 4
Id de la unci´on en decimal ×109
0.0
0.2
0.4
0.6
0.8
1.0
Valo de la endogamia
Umb al m´aximo-m´ınimo - G am´a icas
0.5
0.6
0.7
0.8
0.9
1.0
Figu a 5.23: λ-umb al máximo-mínimo no en elazado pa a g amá icas. Vol e
89

0 1 2 3 4
Id de la unci´on en decimal ×109
0.0
0.2
0.4
0.6
0.8
1.0
Valo de la endogamia
Umb al di ec o-in e so - G am´a icas
0.30
0.35
0.40
0.45
0.50
0.55
0.60
Figu a 5.24: λ-umb al di ec o-in e so no en elazado pa a g amá icas. Vol e
90
0 1 2 3 4
Id de la unci´on en decimal ×109
0.0
0.2
0.4
0.6
0.8
1.0
Valo de la endogamia
Umb al m´aximo-m´ınimo en elazado - G am´a icas
0.0
0.2
0.4
0.6
0.8
1.0
Figu a 5.25: λ-umb al máximo-mínimo en elazado pa a g amá icas. Vol e
91
0 1 2 3 4
Id de la unci´on en decimal ×109
0.0
0.2
0.4
0.6
0.8
1.0
Valo de la endogamia
Umb al di ec o-in e so en elazado - G am´a icas
0.0
0.1
0.2
0.3
0.4
0.5
0.6
Figu a 5.26: λ-umb al di ec o-in e so en elazado pa a g amá icas. Vol e
92
0 1 2 3 4
Id de la unci´on en decimal ×109
0.0
0.2
0.4
0.6
0.8
1.0
Valo de la endogamia
Umb al m´aximo-m´ınimo - Romboides
0.55
0.56
0.57
0.58
0.59
0.60
0.61
Figu a 5.27: λ-umb al máximo-mínimo no en elazado pa a omboides. Vol e
93
0 1 2 3 4
Id de la unci´on en decimal ×109
0.0
0.2
0.4
0.6
0.8
1.0
Valo de la endogamia
Umb al di ec o-in e so - Romboides
0.32
0.33
0.34
0.35
0.36
0.37
0.38
Figu a 5.28: λ-umb al di ec o-in e so no en elazado pa a omboides. Vol e
94

0 1 2 3 4
Id de la unci´on en decimal ×109
0.0
0.2
0.4
0.6
0.8
1.0
Valo de la endogamia
Umb al m´aximo-m´ınimo en elazado - Romboides
0.52
0.54
0.56
0.58
0.60
0.62
Figu a 5.29: λ-umb al máximo-mínimo en elazado pa a omboides. Vol e
95
0 1 2 3 4
Id de la unci´on en decimal ×109
0.0
0.2
0.4
0.6
0.8
1.0
Valo de la endogamia
Umb al di ec o-in e so en elazado - Romboides
0.30
0.32
0.34
0.36
0.38
0.40
0.42
0.44
Figu a 5.30: λ-umb al di ec o-in e so en elazado pa a omboides. Vol e
96
0 1 2 3 4
Id de la unci´on en decimal ×109
0.0
0.2
0.4
0.6
0.8
1.0
Valo de la endogamia
Umb al m´aximo-m´ınimo - 4- omboides
0.44
0.46
0.48
0.50
Figu a 5.31: λ-umb al máximo-mínimo no en elazado pa a 4- omboides. Vol e
97
0 1 2 3 4
Id de la unci´on en decimal ×109
0.0
0.2
0.4
0.6
0.8
1.0
Valo de la endogamia
Umb al di ec o-in e so - 4- omboides
0.322
0.324
0.326
0.328
0.330
0.332
0.334
0.336
0.338
Figu a 5.32: λ-umb al di ec o-in e so no en elazado pa a 4- omboides. Vol e
98
End.
ep esen aci´on
End. colapso
m´ınimo
End. colapso
m´aximo
End. colapso
di ec o
End. colapso
in e so
End. colapso
en elazado
di ec o End. colapso
en elazado
in e so End. colapso
bien elazado Id
End.
ep esen aci´on
End. colapso
m´ınimo
End. colapso
m´aximo
End. colapso
di ec o
End. colapso
in e so
End. colapso
en elazado
di ec o
End. colapso
en elazado
in e so
End. colapso
bien elazado
Id
Todos los ci cui os
−1.00
−0.75
−0.50
−0.25
0.00
0.25
0.50
0.75
1.00
Figu a 5.39: Todos los ci cui os u ilizados. Vol e
105

Anexo IV: G á icas de la sección 5.6
End.
ep esen aci´on
End. colapso
m´aximo
End. colapso
m´ınimo
End. colapso
di ec o
End. colapso
in e so
End. colapso
bien elazado
End. colapso
en elazado
di ec o End. colapso
en elazado
in e so
Endogamia -
Pue as
Op. endogamia -
Pue as
In . endogamia
- Pue as
Co elaciones endogamias s pue as - Ci cui o m´ınimo
−1.00
−0.75
−0.50
−0.25
0.00
0.25
0.50
0.75
1.00
Figu a 5.40: Ci cui os mínimos. Vol e
106
End.
ep esen aci´on
End. colapso
m´aximo
End. colapso
m´ınimo
End. colapso
di ec o
End. colapso
in e so
End. colapso
bien elazado
End. colapso
en elazado
di ec o End. colapso
en elazado
in e so
Endogamia -
Pue as
Op. endogamia -
Pue as
In . endogamia
- Pue as
Co elaciones endogamias s pue as - G am´a icas
−1.00
−0.75
−0.50
−0.25
0.00
0.25
0.50
0.75
1.00
Figu a 5.41: G amá icas. Vol e
107
End.
ep esen aci´on
End. colapso
m´aximo
End. colapso
m´ınimo
End. colapso
di ec o
End. colapso
in e so
End. colapso
bien elazado
End. colapso
en elazado
di ec o End. colapso
en elazado
in e so
Endogamia -
Pue as
Op. endogamia -
Pue as
In . endogamia
- Pue as
Co elaciones endogamias s pue as - Romboides
−1.00
−0.75
−0.50
−0.25
0.00
0.25
0.50
0.75
1.00
Figu a 5.42: Ci cui os con o ma omboidal. Vol e
108
End.
ep esen aci´on
End. colapso
m´aximo
End. colapso
m´ınimo
End. colapso
di ec o
End. colapso
in e so
End. colapso
bien elazado
End. colapso
en elazado
di ec o End. colapso
en elazado
in e so
Endogamia -
Pue as
Op. endogamia -
Pue as
In . endogamia
- Pue as
Co elaciones endogamias s pue as - 4-Romboides
−1.00
−0.75
−0.50
−0.25
0.00
0.25
0.50
0.75
1.00
Figu a 5.43: Ci cui os con o ma 4- omboidal. Vol e
109
Anexo V: G á icas de la sección 5.7
End.
ep esen aci´on
End. colapso
m´aximo
End. colapso
m´ınimo
End. colapso
di ec o
End. colapso
in e so
End. colapso
bien elazado
End. colapso
en elazado
di ec o End. colapso
en elazado
in e so
Reu ilizaci´on
simple
Reu ilizaci´on
compleja
Cocien e
Op. cocien e
Co elaciones compa a i as - Ci cui o m´ınimo s Romboides
−1.00
−0.75
−0.50
−0.25
0.00
0.25
0.50
0.75
1.00
Figu a 5.44: Ci cui os mínimos en e a ci cui os con o ma omboidal. Vol e
110

End.
ep esen aci´on
End. colapso
m´aximo
End. colapso
m´ınimo
End. colapso
di ec o
End. colapso
in e so
End. colapso
bien elazado
End. colapso
en elazado
di ec o End. colapso
en elazado
in e so
Reu ilizaci´on
simple
Reu ilizaci´on
compleja
Cocien e
Op. cocien e
Co elaciones compa a i as - Ci cui o m´ınimo s 4-Romboides
−1.00
−0.75
−0.50
−0.25
0.00
0.25
0.50
0.75
1.00
Figu a 5.45: Ci cui os mínimos en e a ci cui os con o ma 4- omboidal. Vol e
111
End.
ep esen aci´on
End. colapso
m´aximo
End. colapso
m´ınimo
End. colapso
di ec o
End. colapso
in e so
End. colapso
bien elazado
End. colapso
en elazado
di ec o End. colapso
en elazado
in e so
Reu ilizaci´on
simple
Reu ilizaci´on
compleja
Cocien e
Op. cocien e
Co elaciones compa a i as - Ci cui o m´ınimo s G am´a icas
−1.00
−0.75
−0.50
−0.25
0.00
0.25
0.50
0.75
1.00
Figu a 5.46: Ci cui os mínimos en e a g amá icas. Vol e
112
End.
ep esen aci´on
End. colapso
m´aximo
End. colapso
m´ınimo
End. colapso
di ec o
End. colapso
in e so
End. colapso
bien elazado
End. colapso
en elazado
di ec o End. colapso
en elazado
in e so
Reu ilizaci´on
simple
Reu ilizaci´on
compleja
Cocien e
Op. cocien e
Co elaciones compa a i as - G am´a icas s Romboides
−1.00
−0.75
−0.50
−0.25
0.00
0.25
0.50
0.75
1.00
Figu a 5.47: G amá icas en e a ci cui os con o ma 4- omboidal. Vol e
113
End.
ep esen aci´on
End. colapso
m´aximo
End. colapso
m´ınimo
End. colapso
di ec o
End. colapso
in e so
End. colapso
bien elazado
End. colapso
en elazado
di ec o End. colapso
en elazado
in e so
Reu ilizaci´on
simple
Reu ilizaci´on
compleja
Cocien e
Op. cocien e
Co elaciones compa a i as - G am´a icas s 4-Romboides
−1.00
−0.75
−0.50
−0.25
0.00
0.25
0.50
0.75
1.00
Figu a 5.48: G amá icas en e a ci cui os con o ma 4- omboidal. Vol e
114