suma de subconjuntos está en p
TRANSCRIPT
Suma de Subconjuntos está en P
Rodolfo A. Nieves Rivas
Resumen.
En este artículo se presentan dos criterios; los cuales se aplican a un problema NP-completo
importante de la teoría de complejidad conocido como el problema de la suma de
subconjunto; luego se establece su relación a través de dos ejemplos; se concluye con la
efectividad de dichos criterios por cumplir con las condiciones necesarias y suficientes para
tratar este problema de decisión lo que nos conduce en proponer su uso en la elaboración y
diseño de un algoritmo óptimo, dado que la aplicación de dichos criterios permiten resolver
este problema de decisión y garantizan su optimización algorítmica y determinística en
tiempo polinomial.
Palabras claves: Problemas NP-completo; Algoritmo; Criterios.
Abstract.
In this paper we present two criteria, which are applied to an important NP-complete
problem of complexity theory known as the problem of subset sum, then its relationship is
established through two examples, and it is concluded with the effectiveness of such criteria
to meet the conditions necessary and sufficient to address the problem of decision which
leads us to propose its use in the development and design of an optimal algorithm, since the
application of these criteria can solve this decision problem and ensure its algorithmic
optimization and deterministic in polynomial time.
Keywords: NP-complete problems, algorithm, criteria.
Introducción:
Los problemas NP-completos son importantes en teorías de complejidad; decisión y
criptografía así como además otras teorías, a tal grado que es uno de los problemas
considerado por el Instituto de Matematicas Clay como el problema más importante en esta
área sin solución hasta la fecha es el de demostrar si: P=NP.
El problema de la suma de subconjunto pertenece a la categoría NP- completo y resolverlo
es equivalente a resolver todos los de esta categoría. Su enunciado es el siguiente:
“Dado un conjunto de enteros, ¿Existe algún subconjunto no vacío cuya suma sea
exactamente igual a cero?”
Cabe destacar que Stephen Cook y Leonid Levin Formularon la P (Es decir, fácil de
encontrar) contra NP (Es decir, fácil de comprobar) de forma independiente en 1971.
En este artículo se presentan dos criterios que una vez utilizados como certificados
garantizan la solución del objetivo planteado no siendo otro que el de establecer las
condiciones necesarias y suficientes para tratar los problemas considerados NP-completos.
Planteamiento del problema:
El problema de la suma de subconjunto tiene una declaración precisa de la complejidad
lógica de una clase de problemas conocidos como los NP-completos y su enunciado es el
siguiente:
Planteamiento 1:
“Dado un conjunto de enteros, ¿Existe algún subconjunto no vacío cuya suma sea
exactamente igual a cero?”
De forma equivalente se puede plantear así:
Planteamiento 2:
“Dado un conjunto de enteros y un entero: S ¿Existe algún subconjunto cuya suma sea
igual a: S?”
Presentación de Criterios
Su aplicación y análisis de resultados:
Los siguientes criterios tienen como propósito establecer las condiciones necesarias y
suficientes para resolver los dos planteamientos antes expuestos. El criterio 1 permite
abordar el planteamiento 1 y el criterio 2 tiene aplicación en el planteamiento 2 y la
conjugación de ambos permite tratar el problema de la suma de subconjunto.
Criterio 1: La condición necesaria y suficiente para que exista un subconjunto no
vacío: B=0 (Nulo) perteneciente a un conjunto: A cuya suma sea igual a: S (A=S) Solo
es necesario y suficiente que exista un subconjunto: C=S perteneciente al conjunto: A
tal que: A – S = 0 y además que: A - C = 0
Ejemplo 1:
A = {-7 , -3 , -2 , 5 , 8} = 1
S = 1
C = {-7, 8} = 1
B = {-3 , -2 , 5} = 0
A – S = {-7 , -3 , -2 , 5 , 8 , -1} = 0
S = C = { -7 , -3 , -2 , 5 , 8 } = { -7 , 8 } = 1
Criterio 2: Para que exista un subconjunto no vacío ni nulo: C perteneciente a un
conjunto: A cuya suma sea: S solo es necesario y suficiente que: A-C = B tal que: B sea
un subconjunto no vacío ni nulo perteneciente a el conjunto: A
Ejemplo 2:
A = { -7 , -3 , -2 , 5 , 8 } = 1 A = { -7 , -3 , -2 , 5 , 8 } = 1
A = S = 1 A = S = 1
C = 4 C = 3
A – C = B = 1 – 4 = -3 A – C = B = 1 – 3 = -2
B = -3 B = -2
C = {5 , 8 , -7 , -2} = 4 C = {-2 , 5} = 3
Diagrama de flujo y descripción del algoritmo para determinar si existe un
subconjunto no vacío pero nulo en un conjunto dada la suma de sus elementos:
Entrada:
C
Busque:
B = C
SI:
Existe: B
No:
Existe: B
Busque:
C-B = A
Salida:
A = 0
Salida:
No Existe:
A = 0
Diagrama de flujo y descripción del algoritmo para determinar si existe un
subconjunto no vacío pero nulo en un conjunto; dada la suma de sus elementos:
Entrada:
C
Busque:
B = C
SI:
Existe: B No:
Existe: B
Busque:
C-B = A
Salida:
A = 0
Salida:
No Existe:
A = 0
Diagrama de flujo Nº 1
Descripción del algoritmo para determinar si existe un subconjunto no vacío cuya
suma sea: X
En un conjunto, dada la suma de sus elementos: C
Entrada:
C
Busque:
C - X = B
SI:
Existe: B
No:
Existe: B
Busque:
C - B = X
Salida:
A = X
Salida:
No Existe:
A = X
Diagrama de flujo Nº 2
Descripción del algoritmo para determinar si existe un subconjunto no vacío pero
nulo en un conjunto, dada la suma de sus elementos: C
Entrada:
C
Busque:
B = C
SI:
Existe: B
No:
Existe: B
Busque:
C-B = A
Salida:
A = 0
Salida:
No Existe:
A = 0
Análisis de resultados:
Cabe destacar que con el diseño de un algoritmo que contenga ambos criterios como
certificados se lograría la optimización en lo referente a la búsqueda (Problema P) con el
diagrama de flujo Nº 1 el cual describe el criterio 1 y además se garantiza la verificación
(Problema NP) con el diagrama de flujo Nº 2 correspondiente al criterio 2 Los cuales están
fundamentados en los siguientes Teoremas: 1 y 2 comprobándose de esta forma su eficacia
y ejecución en tiempo polinomial.
:1
: !B C
C
Tal que:La suma de los elementos de: C es igual a la suma de los elementos de:B
: A C
Donde: La suma de los elementos de:(A) = 0
Teorema
Si
Entonces
: 2
: !B C
C
Tal que: La diferencia de la suma de los elementos de: C
menos la suma de los elementos de:X
Es igual a la suma de los elementos de:B
: C
Donde:La diferencia de la suma de
Teorema
Si
Entonces X
los elementos de:C
menos la suma de los elementos de:B
Es igual a la suma de los elementos de:X
Conclusión y recomendaciones:
Una vez realizado el análisis correspondiente a los ejemplos presentados anteriormente Se
concluye con reconocer la efectividad de ambos criterios para tratar el problema de la suma
de subconjunto y esto nos permite proponer a la comunidad científica considerar su estudio
y aplicación a problemas análogos y semejantes ampliando de esta forma su optimización y
rango de eficiencia algorítmica. Para lo cual se presentan los siguientes diagramas de flujo
que permiten transformar el problema de la suma de subconjunto NP-completo a un
problema NP y de igual forma de NP-completo a P. Conduciendo este resultado a la
caracterización de criterios que nos garanticen a través de certificados cuando: P = NP
Algoritmo óptimo para búsqueda y verificación de todos los subconjuntos de un
conjunto:
1) y=([-7 -3 -2 5 8])
2) cumsum(y)
3) x1=([y(1)])
4) cumsum(x1)
5) x2=([y(2)])
6) cumsum(x2)
7) x3=([y(3)])
8) cumsum(x3)
9) x4=([y(4)])
10) cumsum(x4)
11) x5=([y(5)])
12) cumsum(x5)
13) x12=([y(1) y(2)])
14) cumsum(x12)
15) x13=([y(1) y(3)])
16) cumsum(x13)
17) x14=([y(1) y(4)])
18) cumsum(x14)
19) x15=([y(1) y(5)])
20) cumsum(x15)
21) x23=([y(2) y(3)])
22) cumsum(x23)
23) x24=([y(2) y(4)])
24) cumsum(x24)
25) x25=([y(2) y(5)])
26) cumsum(x25)
27) x34=([y(3) y(4)])
28) cumsum(x34)
29) x35=([y(3) y(5)])
30) cumsum(x35)
31) x45=([y(4) y(5)])
32) cumsum(x45)
33) x123=([y(1) y(2) y(3)])
34) cumsum(x123)
35) x124=([y(1) y(2) y(4)])
36) cumsum(x124)
37) x125=([y(1) y(2) y(5)])
38) cumsum(x125)
39) x134=([y(1) y(3) y(4)])
40) cumsum(x134)
41) x135=([y(1) y(3) y(5)])
42) cumsum(x135)
43) x145=([y(1) y(4) y(5)])
44) cumsum(x145)
45) x234=([y(2) y(3) y(4)])
46) cumsum(x234)
47) x235=([y(2) y(3) y(5)])
48) cumsum(x235)
49) x245=([y(2) y(4) y(5)])
50) cumsum(x245)
51) x345=([y(3) y(4) y(5)])
52) cumsum(x345)
53) x1234=([y(1) y(2) y(3) y(4)])
54) cumsum(x1234)
55) x1235=([y(1) y(2) y(3) y(5)])
56) cumsum(x1235)
57) x2345=([y(2) y(3) y(4) y(5)])
58) cumsum(x2345)
59) x1345=([y(1) y(3) y(4) y(5)])
60) cumsum(x1345)
61) x1245=([y(1) y(2) y(4) y(5)])
62) cumsum(x1245)
63) x12345=([y(1) y(2) y(3) y(4) y(5)])
64) cumsum(x12345)
Observación: para el diseño de este programa de búsqueda y verificación se utilizó el
lenguaje de programación y aplicación Matlab 6.5 y de los 2N pasos que requiere para
su ejecución donde. N indica los números de elementos del conjunto, cabe destacar
que los pasos de ejecución impares realizan la búsqueda y los pasos de ejecución pares
los verifican.
Diagrama de flujo Nº 1
Descripción del algoritmo para determinar si existe un subconjunto no vacío;
cuya suma sea: X. En un conjunto, dada la suma de sus elementos: C
Entrada:
C
Busque:
C - X = B
SI:
Existe: B
No:
Existe: B
Busque:
C - B = X
Salida:
A = X
Salida:
No Existe:
A = X
Diagrama de flujo Nº 2
Descripción del algoritmo para determinar si existe un subconjunto no vacío pero
nulo en un conjunto, dada la suma de sus elementos: C
Entrada:
C
Busque:
B = C
SI:
Existe: B
No:
Existe: B
Busque:
C-B = A
Salida:
A = 0
Salida:
No Existe:
A = 0
La suma de subconjunto está en P
Problema 1
“Dado un conjunto de enteros, ¿Existe algún subconjunto no vacío cuya suma sea
exactamente igual a cero?”
Problema 2
“Dado un conjunto de enteros y un entero: S ¿Existe algún subconjunto cuya suma
sea igual a: S?”
Reducción:
“Dado un conjunto de enteros: C cuya suma sea igual a: S ¿Existe algún subconjunto:
B perteneciente al conjunto: C cuya suma de sus elementos sea igual a: S?
Criterios y certificados:
“La condición necesaria y suficiente para que en un conjunto de enteros: C cuya suma
sea igual a: S Exista algún subconjunto: B perteneciente al conjunto: C cuya suma de
sus elementos sea igual a: S. Es que exista un subconjunto: A no vacío y perteneciente
al conjunto: C Y cuya suma de sus elementos sea igual a: Cero”
:
: ! B C / C = B
Cuando: A + B = C
Entonces: A C / A = 0
Teorema de existencia
C
Si
:
: ! X C / C - X = B
Cuando: A + B = C
Entonces: A C / A = X
Teorema de existencia
C
Si
Entrada:
C
Busque:
B = C
Si
Existe: B
No
Existe:B
Salida:
Existe:
A=0
Salida:
No existe:
A=0
Entrada:
C y X
Busque:
B = C - X
Si:
Existe B
No:
Existe B
Salida:
Existe: A = X
Salida:
No existe: A = X
Entrada:
C
Busque:
B = C
Si:
Existe B
No:
Existe B
Salida:
Existe: A = 0
Salida:
No existe: A = 0
Referencias Bibliográficas Recomendadas:
Eric Allender, Peter B¨urgisser, Johan Kjeldgaard-Pedersen, and Peter Bro
Miltersen, On the complexity of numerical analysis., SIAM J. Comput. 38 (2009), no.
5, 1987–2006.
B. Adsul, M. Sohoni, and K. V. Subrahmanyam, Quantum deformations of the
restriction of glmn(C)-modules to glm(C) × gln(C), Tech. Report
math.RT/0905.0094v2, arXiv, 2010.
Saugata Basu, A complex analogue of toda’s thoerem., Foundations of Computational
Mathematics (2011), 1–31.
Peter B¨urgisser and Christian Ikenmeyer, Geometric complexity theory and tensor
rank, STOC ’11: 43rd Annual ACM Symposium on Theory of Computing, ACM,
2011, pp. 509–518.
J. Blasiak, K. Mulmuley, and M. Sohoni, Geometric Complexity Theory IV:
nonstandard quantum group for the Kronecker problem, Tech. Report
cs.CC/0703110v3, arXiv, 2011.
Michael Ben-Or and Richard Cleve, Computing algebraic formulas using a constant
number of registers, SIAM J. Comput. 21 (1992), no. 1, 54–58.
Emmanuel Briand, Rosa Orellana, and Mercedes Rosas, Reduced Kronecker
coefficients and counter-examples to Mulmuley’s strong saturation conjecture SH,
Comput. Complexity 18 (2009), no. 4, 577–600, With an appendix by Ketan
Mulmuley.
Michel Brion, Stable properties of plethysm: on two conjectures of Foulkes,
Manuscripta Math. 80 (1993), no. 4, 347–371.
L. Blum, M. Shub, and S. Smale, On a Theory of Computation and Complexity over
the Real Numbers:NP-completeness, Recursive Functions and Universal Machines,
Bulletin of the American Mathematical Society 21 (1989), no. 1, 1–47.
Peter B¨urgisser, The computational complexity of immanants, SIAM J. Comput. 30
(2000), no. 3, 1023–1040 (electronic).
Peter B¨urgisser, The computational complexity to evaluate representations of general
linear groups, SIAM J. Comput. 30 (2000), no. 3, 1010–1022 (electronic).
A. D. Berenstein and A. V. Zelevinsky, Tensor product multiplicities and convex
polytopes in partition space, J. Geom. Phys. 5 (1988), no. 3, 453–472.
Saugata Basu and Thierry Zell, Polynomial hierarchy, betti numbers, and a real
analogue of toda’s theorem., Foundations of Computational Mathematics 10 (2010),
no. 4, 429–454.
Calin Chindris, Harm Derksen, and Jerzy Weyman, Counterexamples to Okounkov’s
log-concavity conjecture, Compos. Math. 143 (2007), no. 6, 1545–1557.
Felipe Cucker, Michael Shub, and Steve Smale, Separation of complexity classes in
Koiran’s weak model., Theoretical Computer Science 133 (1994), 3–14.
Qi Cheng, Sergey P. Tarasov, and Mikhail N. Vyalyi, Efficient algorithms for sparse
cyclotomic integer zero testing, Theory Comput. Syst. 46 (2010), no. 1, 120–142.
Igor V. Dolgachev and Yi Hu, Variation of geometric invariant theory quotients, Inst.
Hautes ´ Etudes Sci. Publ. Math. (1998), no. 87, 5–56, With an appendix by Nicolas
Ressayre.
Jiri Dadok and Victor Kac, Polar representations, J. Algebra 92 (1985), no. 2, 504–
524.
Martin Davis, Yuri Matiyasevich, and Julia Robinson, Hilbert’s tenth problem:
Diophantine equations: Positive aspects of a negative solution, Proceedings of
Symposia in Pure Mathematics 28 (1976), 323–378.
G. Frobenius, Uber die Darstellung der endlichen Gruppen durch lineare
Substitutionen, Sitzungsber Deutsch. Akad. Wiss. Berlin (1897), 994–1015.
Bruno Grenet, An upper bound for the permanent versus determinant problem,
Manuscript.
Leonid Gurvits, Classical complexity and quantum entanglement, J. Comput. System
Sci. 69 (2004), no. 3, 448–484.
Leonid Gurvits, Combinatorial and algorithmic aspects of hyperbolic polynomials,
Tech. Report math.CO/0404474, arXiv, 2004.
Leonid Gurvits, Hyperbolic polynomials approach to van der Waerden/Schrijver–
Valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications,
STOC ’06: 38th Annual ACM Symposium on Theory of Computing, ACM, 2006, pp.
417–426.
Roger Howe, (GLn,GLm)-duality and symmetric plethysm, Proc. Indian Acad. Sci.
Math. Sci. 97 (1987), no. 1-3, 85–109 (1988).
V. G. Kac, Some remarks on nilpotent orbits, J. Algebra 64 (1980), no. 1, 190–213.
Pascal Koiran, A weak version of the Blum, Shub, and Smale model., FOCS ’93: 33rd
Annual IEEE Symposium on Foundations of Computer Science, 1993, pp. 486–495.
Pascal Koiran, Hilbert’s nullstellensatz is in the polynomial hierarchy., Journal of
Complexity 12 (1996), no. 4, 273–286.
Pascal Koiran and Sylvain Perifel, Vpspace and a transfer theorem over the reals.,
STOC ’07: 24th Annual ACM Symposium on Theory of Computing, Springer-Verlag
Berlin, Heidelberg, 2007, pp. 417–428.
Masaki Kashiwara and Pierre Schapira, Sheaves on manifolds, Grundlehren der
Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences],
vol. 292, Springer-Verlag, Berlin, 1990, With a chapter in French by Christian
Houzel.
Allen Knutson and Terence Tao, The honeycomb model of GLn(C) tensor products. I.
Proof of the saturation conjecture, J. Amer. Math. Soc. 12 (1999), no. 4, 1055–1090.
Shrawan Kumar, Geometry of orbits of permanents and determinants, Tech. Report
math.AG/1007.1695, arXiv, 2010.
Shrawan Kumar, A study of the representations supported by the orbit closure of the
determinant, Tech. Report math.RT/1109.5996, arXiv, 2011.
J. M. Landsberg, Laurent Manivel, and Nicolas Ressayre, Hypersurfaces with
degenerate duals and the Geometric Complexity Theory Program, Tech. Report
math.AG/1004.4802, arXiv, 2010.
Laurent Manivel, Applications de Gauss et pl´ethysme, Ann. Inst. Fourier (Grenoble)
47 (1997), no. 3, 715–773.
L. Manivel, Gaussian maps and plethysm, Algebraic geometry (Catania,
1993/Barcelona, 1994), Lecture Notes in Pure and Appl. Math., vol. 200, Dekker, New
York, 1998, pp. 91–117.
Yuri Matiyasevich, Enumerable sets are diophantine, Soviet Mathematics (1970), no.
2, 354–357.
Stephan Mertens and Christopher Moore, The complexity of the fermionant, and
immanants of constant width, Tech. Report cs.CC/1110.1821, arXiv, 2011.
Thierry Mignon and Nicolas Ressayre, A quadratic bound for the determinant and
permanent problem, Int. Math. Res. Not. (2004), no. 79, 4241–4253.
Ketan D. Mulmuley and Milind Sohoni, Geometric complexity theory I: an approach
to the P vs. NP and related problems, SIAM J. Comput. 31 (2001), no. 2, 496–526.
Ketan D. Mulmuley and Milind Sohoni, Geometric complexity theory II: towards
explicit obstructions for embeddings among class varieties, SIAM J. Comput. 38
(2008), no. 3, 1175–1206.
Ketan D. Mulmuley, Geometric Complexity Theory VI: the flip via positivity, Tech.
report, Department of Computer Science, The University of Chicago, 2011.
Andrei Okounkov, Why would multiplicities be log-concave?, Tech. Report
math.RT/0002085, arXiv, 2000.
Kenneth W. Regan, Polynomials and combinatorial definitions of languages,
Complexity theory retrospective, II, Springer, New York, 1997, pp. 261–293.
N. Ressayre, Geometric invariant theory and the generalized eigenvalue problem,
Invent. Math. 180 (2010), no. 2, 389–441.
Mike Shub and Steve Smale, On the intractibilit of hilbert’s nullstellensatz and an
algebraic version of ’np not equal to p?’, Duke Math J. 81 (1995), 47–54.
Seinosuke Toda, Pp is as hard as the polynomial-time hierarchy., SIAM Journal on
Computing 20 (1991), no. 2, 865–877.
Leslie Valiant, Completeness classes in algebra, STOC ’79: 11th Annual ACM
Symposium on Theory of Computing, ACM, 1979, pp. 249–261.
Ke Ye, The stabilizer of immanants, Linear Algebra Appl. 435 (2011), no. 5, 1085–
1098.