Problema de suma de subconjuntos

Problema de decisión en informática.

El problema de la suma de subconjuntos (SSP) es un problema de decisión en informática . En su formulación más general, hay un conjunto múltiple de números enteros y una suma objetivo , y la cuestión es decidir si algún subconjunto de números enteros suma exactamente . ^[1] Se sabe que el problema es NP-completo . Además, algunas variantes restringidas también son NP-completas, por ejemplo: ^[1] ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle T}$

• La variante en la que todas las entradas son positivas.
• La variante en la que las entradas pueden ser positivas o negativas, y . Por ejemplo, dado el conjunto , la respuesta es sí porque el subconjunto suma cero. ${\displaystyle T=0}$ ${\displaystyle \{-7,-3,-2,9000,5,8\}}$ ${\displaystyle \{-3,-2,5\}}$
• La variante en la que todas las entradas son positivas y la suma objetivo es exactamente la mitad de la suma de todas las entradas, es decir, . Este caso especial de SSP se conoce como problema de partición . ${\displaystyle T={\frac {1}{2}}(a_{1}+\dots +a_{n})}$

SSP también puede considerarse como un problema de optimización : encontrar un subconjunto cuya suma sea como máximo T y, sujeto a eso , lo más cercano posible a T. Es NP-difícil, pero existen varios algoritmos que pueden resolverlo razonablemente rápido en la práctica.

SSP es un caso especial del problema de la mochila y del problema de la suma de subconjuntos múltiples .

Dureza computacional

La complejidad del tiempo de ejecución de SSP depende de dos parámetros:

• n - el número de números enteros de entrada. Si n es un número fijo pequeño, entonceses práctica una búsqueda exhaustiva de la solución.
• L : la precisión del problema, expresada como el número de valores posicionales binarios que se necesitan para plantear el problema. Si L es un número fijo pequeño, entonces existen algoritmos de programación dinámica que pueden resolverlo exactamente.

A medida que tanto n como L crecen, el SSP es NP-duro. La complejidad de los algoritmos más conocidos es exponencial en el menor de los dos parámetros n y L. El problema es NP-difícil incluso cuando todos los números enteros de entrada son positivos (y la suma objetivo T es parte de la entrada). Esto se puede demostrar mediante una reducción directa de 3SAT . ^[2] También se puede demostrar mediante reducción del emparejamiento tridimensional (3DM): ^[3]

• Se nos da una instancia de 3DM, donde los conjuntos de vértices son W, X, Y. Cada conjunto tiene n vértices. Hay m aristas, donde cada arista contiene exactamente un vértice de cada uno de W, X, Y. Denota L  := techo(log ₂ ( m +1)), de modo que L es mayor que el número de bits necesarios para representar la número de aristas.
• Construimos una instancia de SSP con m enteros positivos. Los números enteros se describen por su representación binaria. Cada número entero de entrada se puede representar mediante 3 nL bits, divididos en 3 n zonas de L bits. Cada zona corresponde a un vértice.
• Para cada borde (w,x,y) en la instancia 3DM, hay un número entero en la instancia SSP, en el que exactamente tres bits son "1": los bits menos significativos en las zonas de los vértices w, x y y. Por ejemplo, si n =10 y L=3, y W=(0,...,9), X=(10,...,19), Y=(20,...,29), entonces la arista (0, 10, 20) está representada por el número (2 ⁰ +2 ³⁰ +2 ⁶⁰ ).
• La suma objetivo T en la instancia de SSP se establece en un número entero con "1" en el bit menos significativo de cada zona, es decir, (2 ⁰ +2 ¹ +...+2 ^3n-1 ).
• Si la instancia 3DM tiene una coincidencia perfecta, entonces la suma de los enteros correspondientes en la instancia SSP produce exactamente T.
• Por el contrario, si la instancia de SSP tiene un subconjunto con suma exactamente T, entonces, dado que las zonas son lo suficientemente grandes como para que no haya "transportes" de una zona a la siguiente, la suma debe corresponder a una coincidencia perfecta en la instancia de 3DM.

También se sabe que las siguientes variantes son NP-duras:

• Los números enteros de entrada pueden ser tanto positivos como negativos, y la suma objetivo T = 0. Esto se puede demostrar reduciendo a partir de la variante con números enteros positivos. Denote esa variante por SubsetSumPositive y la variante actual por SubsetSumZero. Dada una instancia ( S , T ) de SubsetSumPositive, construya una instancia de SubsetSumZero agregando un solo elemento con valor − T . Dada una solución para la instancia SubsetSumPositive, agregar − T produce una solución para la instancia SubsetSumZero. Por el contrario, dada una solución a la instancia SubsetSumZero, debe contener − T (ya que todos los números enteros en S son positivos), por lo que para obtener una suma de cero, también debe contener un subconjunto de S con una suma de + T , que es una solución de la instancia SubsetSumPositive.
• Los números enteros de entrada son positivos y T = suma ( S )/2. Esto también puede demostrarse mediante reducción de la variante general; ver problema de partición .

El problema de conteo análogo #SSP, que solicita enumerar el número de subconjuntos que se suman al objetivo, es #P-completo . ^[4]

Algoritmos de tiempo exponencial

Hay varias formas de resolver SSP en tiempo exponencial en n . ^[5]

Exclusión inclusión

El algoritmo más ingenuo sería recorrer todos los subconjuntos de n números y, para cada uno de ellos, comprobar si la suma del subconjunto da el número correcto. El tiempo de ejecución es de orden , ya que hay subconjuntos y, para comprobar cada subconjunto, necesitamos sumar como máximo n elementos. ${\displaystyle O(2^{n}\cdot n)}$ ${\displaystyle 2^{n}}$

El algoritmo se puede implementar mediante una búsqueda en profundidad de un árbol binario: cada nivel del árbol corresponde a un número de entrada; la rama izquierda corresponde a excluir el número del conjunto, y la rama derecha corresponde a incluir el número (de ahí el nombre Inclusión-Exclusión). La memoria requerida es . El tiempo de ejecución se puede mejorar mediante varias heurísticas: ^[5] ${\displaystyle O(n)}$

• Procese los números de entrada en orden descendente.
• Si los números enteros incluidos en un nodo determinado exceden la suma del mejor subconjunto encontrado hasta el momento, el nodo se poda.
• Si los números enteros incluidos en un nodo determinado, más todos los números enteros restantes, son menores que la suma del mejor subconjunto encontrado hasta el momento, el nodo se poda.

Horowitz y Sahni

En 1974, Horowitz y Sahni ^[6] publicaron un algoritmo de tiempo exponencial más rápido, que se ejecuta en el tiempo , pero requiere mucho más espacio . El algoritmo divide arbitrariamente los n elementos en dos conjuntos de cada uno. Para cada uno de estos dos conjuntos, almacena una lista de las sumas de todos los subconjuntos posibles de sus elementos. Luego se ordena cada una de estas dos listas. Utilizar incluso el algoritmo de clasificación por comparación más rápido, Mergesort para este paso llevaría tiempo . Sin embargo, dada una lista ordenada de sumas de elementos, la lista se puede expandir a dos listas ordenadas con la introducción de un ( )ésimo elemento, y estas dos listas ordenadas se pueden fusionar en el tiempo . Por lo tanto, cada lista se puede generar ordenada en el tiempo . Dadas las dos listas ordenadas, el algoritmo puede verificar si un elemento de la primera matriz y un elemento de la segunda matriz suman T en el tiempo . Para hacer eso, el algoritmo pasa por la primera matriz en orden decreciente (comenzando por el elemento más grande) y la segunda matriz en orden creciente (comenzando por el elemento más pequeño). Siempre que la suma del elemento actual en la primera matriz y el elemento actual en la segunda matriz sea mayor que T , el algoritmo pasa al siguiente elemento de la primera matriz. Si es menor que T , el algoritmo pasa al siguiente elemento de la segunda matriz. Si se encuentran dos elementos que suman T , se detiene. (El subproblema de la suma de dos elementos se conoce como suma de dos. ^[7] ) ${\displaystyle O(2^{n/2}\cdot (n/2))}$ ${\displaystyle O(2^{n/2})}$ ${\displaystyle n/2}$ ${\displaystyle 2^{n/2}}$ ${\displaystyle O(2^{n/2}n)}$ ${\displaystyle k}$ ${\displaystyle k+1}$ ${\displaystyle O(2^{k})}$ ${\displaystyle O(2^{n/2})}$ ${\displaystyle O(2^{n/2})}$

Schroeppel y Shamir

En 1981, Schroeppel y Shamir presentaron un algoritmo ^[8] basado en Horowitz y Sanhi, que requiere un tiempo de ejecución similar (y mucho menos espacio) . En lugar de generar y almacenar todos los subconjuntos de n /2 elementos por adelantado, dividen los elementos en 4 conjuntos de n /4 elementos cada uno y generan subconjuntos de n /2 pares de elementos dinámicamente usando un montón mínimo , lo que produce el tiempo y el tiempo anteriores. complejidades espaciales ya que esto se puede hacer en un espacio dadas 4 listas de longitud k. ${\displaystyle O(2^{n/2}\cdot (n/4))}$ ${\displaystyle O(2^{n/4})}$ ${\displaystyle O(k^{2}\log(k))}$ ${\displaystyle O(k)}$

Debido a los requisitos de espacio, el algoritmo HS es práctico para hasta 50 enteros aproximadamente y el algoritmo SS es práctico para hasta 100 enteros. ^[5]

Howgrave-Graham y Joux

En 2010, Howgrave-Graham y Joux ^[9] presentaron un algoritmo probabilístico que se ejecuta más rápido que todos los anteriores: en el tiempo utilizando el espacio . Resuelve solo el problema de decisión, no puede probar que no hay solución para una suma determinada y no devuelve la suma del subconjunto más cercano a T. ${\displaystyle O(2^{0.337n})}$ ${\displaystyle O(2^{0.256n})}$

Las técnicas de Howgrave-Graham y Joux se ampliaron posteriormente ^[10] llevando la complejidad temporal a . ${\displaystyle O(2^{0.291n})}$

Soluciones de programación dinámica de tiempo pseudopolinomial

SSP se puede resolver en tiempo pseudopolinomial mediante programación dinámica . Supongamos que tenemos la siguiente secuencia de elementos en una instancia:

${\displaystyle x_{1},\ldots ,x_{N}}$

Definimos un estado como un par ( i , s ) de números enteros. Este estado representa el hecho de que

"hay un subconjunto no vacío cuya suma es s ". ${\displaystyle x_{1},\ldots ,x_{i}}$

Cada estado ( i , s ) tiene dos estados siguientes:

• ( i +1, s ), lo que implica que no está incluido en el subconjunto; ${\displaystyle x_{i+1}}$
• ( i +1, s + ), lo que implica que está incluido en el subconjunto. ${\displaystyle x_{i+1}}$ ${\displaystyle x_{i+1}}$

A partir del estado inicial (0, 0), es posible utilizar cualquier algoritmo de búsqueda de gráficos (por ejemplo, BFS ) para buscar el estado ( N , T ). Si se encuentra el estado, retrocediendo podemos encontrar un subconjunto con una suma de exactamente T.

El tiempo de ejecución de este algoritmo es como máximo lineal en el número de estados. El número de estados es como máximo N veces el número de sumas posibles diferentes. Sea A la suma de los valores negativos y B la suma de los valores positivos; el número de sumas posibles diferentes es como máximo B - A , por lo que el tiempo de ejecución total es . Por ejemplo, si todos los valores de entrada son positivos y están limitados por alguna constante C , entonces B es como máximo NC , por lo que el tiempo requerido es . ${\displaystyle O(N(B-A))}$ ${\displaystyle O(N^{2}C)}$

Esta solución no cuenta como tiempo polinomial en la teoría de la complejidad porque no es polinomial en el tamaño del problema, que es el número de bits utilizados para representarlo. Este algoritmo es polinómico en los valores de A y B , los cuales son exponenciales en su número de bits. Sin embargo, la suma del subconjunto codificada en unario está en P, ya que entonces el tamaño de la codificación es lineal en BA. Por lo tanto, la suma del subconjunto es sólo débilmente NP-completa. ${\displaystyle B-A}$

Para el caso de que cada uno sea positivo y esté limitado por una constante fija C , en 1999, Pisinger encontró un algoritmo de tiempo lineal que tiene complejidad temporal (tenga en cuenta que esto es para la versión del problema donde la suma objetivo no es necesariamente cero, ya que de lo contrario el el problema sería trivial). ^[11] En 2015, Koiliaris y Xu encontraron un algoritmo determinista para el problema de suma de subconjuntos donde T es la suma que necesitamos encontrar. ^[12] En 2017, Bringmann encontró un algoritmo de tiempo aleatorio. ^[13] ${\displaystyle x_{i}}$ ${\displaystyle O(NC)}$ ${\displaystyle {\tilde {O}}(T{\sqrt {N}})}$ ${\displaystyle {\tilde {O}}(T+N)}$

En 2014, Curtis y Sanches encontraron una recursividad simple altamente escalable en máquinas SIMD que tienen tiempo y espacio, donde p es el número de elementos de procesamiento y es el número entero más bajo. ^[14] Esta es la mejor complejidad teórica paralela conocida hasta ahora. ${\displaystyle O(N(m-x_{\min })/p)}$ ${\displaystyle O(N+m-x_{\min })}$ ${\displaystyle m=\min(s,\sum x_{i}-s)}$ ${\displaystyle x_{\min }}$

Curtis y Sanches analizan una comparación de los resultados prácticos y la solución de casos difíciles del SSP. ^[15]

Algoritmos de aproximación de tiempo polinomial

Supongamos que todas las entradas son positivas. Un algoritmo de aproximación a SSP tiene como objetivo encontrar un subconjunto de S con una suma de como máximo T y al menos r veces la suma óptima, donde r es un número en (0,1) llamado relación de aproximación .

1/2-aproximación simple

El siguiente algoritmo muy simple tiene una relación de aproximación de 1/2: ^[16]

• Ordene las entradas por valor descendente;
• Coloque la siguiente entrada más grande en el subconjunto, siempre que quepa allí.

Cuando este algoritmo termina, o todas las entradas están en el subconjunto (lo cual obviamente es óptimo) o hay una entrada que no encaja. La primera de estas entradas es más pequeña que todas las entradas anteriores que están en el subconjunto y la suma de las entradas en el subconjunto es mayor que T /2; de lo contrario, la entrada también es menor que T/2 y encajaría en el conjunto. Una suma así superior a T/2 es obviamente superior a OPT/2.

Esquema de aproximación de tiempo totalmente polinomial

El siguiente algoritmo logra, para cada , una relación de aproximación de . Su tiempo de ejecución es polinomio en n y . Recuerde que n es el número de entradas y T es el límite superior de la suma del subconjunto. ${\displaystyle \epsilon >0}$ ${\displaystyle (1-\epsilon )}$ ${\displaystyle 1/\epsilon }$

inicializa una lista L para que contenga un elemento 0.para cada  i de 1 an, sea U i una lista que contenga todos los elementos y en L , y todas las sumas x i + y para todos y en L. ordenar U i en orden ascendente dejar L vacío sea ​​y el elemento más pequeño de U i agregue y a L  para cada elemento z de U i en orden creciente haga  // Recorte la lista eliminando números cercanos entre sí  // y descarte elementos mayores que la suma objetivo T .  si  y + ε T / n < z ≤ T  entonces  y = z suma z a Ldevolver el elemento más grande en L.

Tenga en cuenta que sin el paso de recorte (el bucle interno "para cada"), la lista L contendría las sumas de todos los subconjuntos de entradas. El paso de recorte hace dos cosas: ${\displaystyle 2^{n}}$

• Garantiza que todas las sumas restantes en L estén por debajo de T , por lo que son soluciones factibles al problema de suma de subconjuntos.
• Asegura que la lista L sea "escasa", es decir, que la diferencia entre cada dos sumas parciales consecutivas sea al menos . ${\displaystyle \epsilon T/n}$

Estas propiedades juntas garantizan que la lista L no contenga más que elementos; por lo tanto, el tiempo de ejecución es polinómico en . ${\displaystyle n/\epsilon }$ ${\displaystyle n/\epsilon }$

Cuando finaliza el algoritmo, si la suma óptima está en L , se devuelve y terminamos. En caso contrario, deberá haber sido eliminado en un paso de recorte previo. Cada paso de recorte introduce un error aditivo de como máximo , por lo que n pasos juntos introducen un error de como máximo . Por lo tanto, la solución devuelta es al menos cual es al menos . ${\displaystyle \epsilon T/n}$ ${\displaystyle \epsilon T}$ ${\displaystyle {\text{OPT}}-\epsilon T}$ ${\displaystyle (1-\epsilon ){\text{OPT}}}$

El algoritmo anterior proporciona una solución exacta a SSP en el caso de que los números de entrada sean pequeños (y no negativos). Si cualquier suma de números se puede especificar con como máximo P bits, entonces resolver el problema aproximadamente con es equivalente a resolverlo exactamente. Entonces, el algoritmo de tiempo polinómico para la suma aproximada de subconjuntos se convierte en un algoritmo exacto con tiempo de ejecución polinómico en n y (es decir, exponencial en P ). ${\displaystyle \epsilon =2^{-P}}$ ${\displaystyle 2^{P}}$

Kellerer, Mansini, Pferschy y Speranza ^[17] y Kellerer, Pferschy y Pisinger ^[18] presentan otros FPTAS para la suma del subconjunto.

Ver también

• Problema de mochila  : problema de optimización combinatoria: una generalización de SSP en la que cada elemento de entrada tiene tanto un valor como un peso. El objetivo es maximizar el valor sujeto a un límite en el peso total .
• Problema de suma de subconjuntos múltiples : una generalización de SSP en la que se deben elegir varios subconjuntos.
• 3SUM  – Problema en la teoría de la complejidad computacional
• Criptosistema de mochila Merkle-Hellman  : uno de los primeros criptosistemas de clave pública inventado por Ralph Merkle y Martin Hellman en 1978. Las ideas detrás de él son más simples que las que involucran RSA, y se ha roto.Pages displaying wikidata descriptions as a fallback

Referencias

1. Kleinberg, Jon; Tardos, Éva (2006). Diseño de algoritmos (2ª ed.). pag. 491.ISBN​ 0-321-37291-3.
2. Goodrich, Michael. "Más problemas de NP completos y NP difíciles" (PDF) . Archivado (PDF) desde el original el 9 de octubre de 2022.
3. Garey, Michael R .; Johnson, David S. (1979). Computadoras e intratabilidad: una guía para la teoría de la integridad NP . Serie de libros de ciencias matemáticas (1ª ed.). Nueva York: WH Freeman and Company . ISBN 9780716710455. SEÑOR  0519066. OCLC  247570676., Sección 3.1 y problema SP1 en el Apéndice A.3.1.
4. Filmus, Yuval (30 de enero de 2016). Responda a: "¿Existe un algoritmo rápido y conocido para contar todos los subconjuntos que suman menos de un número determinado?". Intercambio de pilas teóricas de informática . Tenga en cuenta la cita de Filmus en apoyo de la afirmación (Faliszewski, Piotr; Hemaspaandra, Lane (2009). "The complex of power-index comparation". Theoretical Computer Science . Elsevier. 410 : 101-107. DOI 10.1016/j.tcs .2008.09.034) de hecho no prueba la afirmación, sino que dirige a los lectores a otra cita ( Papadimitriou, Christos (1994). Complejidad computacional. Addison-Wesley: Reading, MA. Capítulo 9. ISBN 0-201-53082-1  ​​- a través de Internet Archive ), que tampoco prueba explícitamente la afirmación. Sin embargo , la prueba de Papadimitriou de que SSP es NP-completo mediante la reducción de 3SAT se generaliza a una reducción de #3SAT a #SSP. 
5. Richard E. Korf, Ethan L. Schreiber y Michael D. Moffitt (2014). "Partición óptima de números multidireccionales secuenciales" (PDF) . Archivado (PDF) desde el original el 9 de octubre de 2022.{{cite web}}: CS1 maint: multiple names: authors list (link)
6. Horowitz, Ellis; Sahni, Sartaj (1974). «Cálculo de particiones con aplicaciones al problema de la mochila» (PDF) . Revista de la Asociación de Maquinaria de Computación . 21 (2): 277–292. doi :10.1145/321812.321823. hdl : 1813/5989 . SEÑOR  0354006. S2CID  16866858. Archivado (PDF) desde el original el 9 de octubre de 2022.
7. "El problema de las dos sumas" (PDF) . Archivado (PDF) desde el original el 9 de octubre de 2022.
8. Schroeppel, Richard; Shamir, Adi (1 de agosto de 1981). "Algoritmo AT = O(2n/2), S = O(2n/4) para ciertos problemas NP-completos". Revista SIAM de Computación . 10 (3): 456–464. doi :10.1137/0210033. ISSN  0097-5397.
9. Howgrave-Graham, Nick; Joux, Antoine (2010). "Nuevos algoritmos genéricos para mochilas duras". En Gilbert, Henri (ed.). Avances en Criptología – EUROCRYPT 2010 . Apuntes de conferencias sobre informática. vol. 6110. Berlín, Heidelberg: Springer. págs. 235-256. doi : 10.1007/978-3-642-13190-5_12 . ISBN 978-3-642-13190-5.
10. Becker, Anja; Joux, Antoine (2010). "Algoritmos genéricos mejorados para mochilas duras". En Gilbert, Henri (ed.). Avances en Criptología – EUROCRYPT 2011 . Apuntes de conferencias sobre informática. vol. 6632. Berlín, Heidelberg: Springer. págs. 364–385. doi : 10.1007/978-3-642-20465-4_21 . ISBN 978-3-642-20465-4.
11. Pisinger, David (1999). "Algoritmos de tiempo lineal para problemas de mochila con pesos acotados". Revista de algoritmos . 33 (1): 1–14. doi :10.1006/jagm.1999.1034. SEÑOR  1712690.
12. Koiliaris, Konstantinos; Xu, Chao (8 de julio de 2015). "Un algoritmo de tiempo pseudopolinomial más rápido para la suma de subconjuntos". arXiv : 1507.02318 [cs.DS].
13. Bringmann, Karl (2017). "Un algoritmo de tiempo pseudopolinomial casi lineal para la suma de subconjuntos". En Klein, Philip N. (ed.). Actas del vigésimo octavo simposio anual ACM-SIAM sobre algoritmos discretos (SODA 2017) . SIAM. págs. 1073-1084. arXiv : 1610.04712 . doi :10.1137/1.9781611974782.69.
14. Curtis, VV; Sanches, CAA (enero de 2016). "Una solución eficiente al problema de la suma de subconjuntos en GPU: una solución eficiente al problema de la suma de subconjuntos en GPU". Concurrencia y Computación: Práctica y Experiencia . 28 (1): 95-113. doi :10.1002/cpe.3636. S2CID  20927927.
15. Curtis, VV; Sanches, CAA (julio de 2017). "Un algoritmo de poco espacio para el problema de suma de subconjuntos en GPU". Investigación de operaciones y computadoras . 83 : 120-124. doi :10.1016/j.cor.2017.02.006.
16. Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (1 de febrero de 2000). "El problema de la suma de subconjuntos múltiples". Revista SIAM sobre Optimización . 11 (2): 308–319. doi :10.1137/S1052623498348481. ISSN  1052-6234.
17. Kellerer, Hans; Mansini, Renata; Pferschy, Ulrich; Esperanza, María Grazia (1 de marzo de 2003). "Un esquema de aproximación totalmente polinomial eficiente para el problema de suma de subconjuntos". Revista de Ciencias de la Computación y de Sistemas . 66 (2): 349–370. doi :10.1016/S0022-0000(03)00006-0. ISSN  0022-0000.
18. Hans Kellerer; Ulrich Pferschy; David Pisinger (2004). Problemas con la mochila. Saltador. pag. 97.ISBN​ 9783540402862.

Otras lecturas

• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001) [1990]. "35.5: El problema de la suma de subconjuntos". Introducción a los algoritmos (2ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-03293-7.
• Michael R. Garey y David S. Johnson (1979). Computadoras e intratabilidad: una guía para la teoría de la integridad NP . WH Freeman. ISBN 0-7167-1045-5.A3.2: SP13, pág.223.
• Lagarias, JC; Odlyzko, AM (1 de enero de 1985). "Resolver problemas de suma de subconjuntos de baja densidad". Revista de la ACM . 32 (1): 229–246. doi : 10.1145/2455.2461 . ISSN  0004-5411. S2CID  885632.
• Martello, Silvano; Toth, Paolo (1990). "4 Problema de suma de subconjuntos". Problemas de mochila: algoritmos e interpretaciones informáticas . Wiley-Interscience. págs. 105-136. ISBN 0-471-92420-2. SEÑOR  1086874.