Problema de la partición

Problema de la partición

En ciencias de la computación, el Problema de la partición es un problema NP-completo, que visto como un problema de decisión, consiste en decidir si, dado un multiconjunto de números enteros, puede éste ser particionado en dos "mitades" tal que sumando los elementos de cada una, ambas den como resultado la misma suma.

Más precisamente, dado un multiconjunto S de enteros: ¿existe alguna forma de particionar S en dos subconjuntos S1 y S2, tal que la suma de los elementos en S1 sea igual que la suma de los elementos en S2?

El problema de partición es equivalente a un caso particular del problema de la suma de subconjuntos, el cual dice: dado un conjunto S de enteros, ¿existe algún subconjunto S1 de S cuyos elementos suman exactamente t /2, donde t es la suma de todos los elementos de S? La equivalencia puede verse definiendo S2 como la diferencia S − S1. Por lo tanto, la solución con programación dinámica existente para resolver el problema de suma de subconjuntos, utilizando tiempo pseudo-polinomial, también es aplicable al problema de partición.

Una variación de este problema es el problema de 3-partición, en donde el conjunto S debe particionarse en |S|/3 subconjuntos que sumen lo mismo. A diferencia del problema de partición, este problema no es resoluble en tiempo pseudo-polinomial, a menos que P = NP: esto porque el problema de 3-partición permanece en la clase NP-completa incluso utilizando codificación unaria.

Véase también

Referencias

Obtenido de "Problema de la partici%C3%B3n"

Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Problema de la 3-partición — Saltar a navegación, búsqueda En ciencias de la computación, el Problema de 3 partición es un problema NP completo, que consiste en decidir si dado un multiconjunto S de n = 3m enteros positivos, puede ser particionado en m subconjuntos S1, S2, … …   Wikipedia Español

  • Problema de la división de un conjunto — En complejidad computacional, el problema de división de un conjunto (más comúnmente conocido en inglés como Set splitting problem) es el siguiente problema de decisión: dada una familia F de subconjuntos de un conjunto finito S, ¿existe una… …   Wikipedia Español

  • Partición binaria del espacio — Binary space partitioning o Partición Binaria del Espacio (BSP) es un método para subdividir recursivamente un espacio en elementos convexos empleando hiperplanos. Esta subdivisión da lugar a una representación de la escena por medio de una… …   Wikipedia Español

  • Primer Tratado de Partición — El Primer Tratado de Partición (también conocido como Tratado de La Haya) fue un tratado firmado el 11 de octubre de 1698 entre Inglaterra y Francia. El tratado era un intento de resolver el problema de sucesión al trono español y proponía como… …   Wikipedia Español

  • Lista de 21 problemas NP-completos de Karp — Por Lista de 21 problemas NP completos de Karp se entiende a una lista de 21 problemas computacionales famosos, que tratan sobre combinatoria y teoría de grafos, y que cumplen la característica en común de que todos ellos pertenecen a la clase de …   Wikipedia Español

  • Carl Zeiss — Saltar a navegación, búsqueda Carl Zeiss a sus 47 años de vida Carl Zeiss (11 de septiembre de 1816 – 3 de diciembre de 1888) fue un óptico muy comúnmente conocido por la compañía que fundó y que lleva su apellido: Zeiss (actualmente Carl Zeiss… …   Wikipedia Español

  • Método de los elementos finitos — Solución de MEF en 2D para una configuración de un magnetostato, (las líneas muestran la dirección de la densidad de flujo calculada, y el color, su magnitud) …   Wikipedia Español

  • Nakba — Refugiados palestinos en 1948. Nakba es un término árabe (النكبة) que significa catástrofe o desastre , utilizado para designar al éxodo palestino (en árabe الهجرة الفلسطينية, al Hijra al Filasteeniya). Según la Agencia de las Naciones Unidas… …   Wikipedia Español

  • Guerra Civil durante el Mandato de Palestina — Parte de Conflicto árabe israelí Fecha 30 de noviembre de 1947 – …   Wikipedia Español

  • Modelo de Ising — El modelo de Ising es un modelo físico propuesto para estudiar el comportamiento de materiales ferromagnéticos. Se trata de un modelo paradigmático de la Mecánica Estadística, en parte porque fue uno de los primeros en aparecer, pero sobre todo… …   Wikipedia Español


Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.