Problema de la división de un conjunto
- 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 partición de S en dos subconjuntos S1 y S2 tales que ninguno de los elementos de F esté completamente en S1 o S2? Este problema es NP-completo.[1]
Visto como un problema de optimización, se llama el problema de división del máximo conjunto (en inglés Max Set Splitting) y consiste en encontrar la partición que maximiza el número de elementos divididos de F. Este es un problema APX[2] (y NP-hard). El problema sigue siendo NP-hard incluso si todos los subconjuntos de F contienen el mismo número de elementos, todos ellos mayores que 1.[3]
Como problema de decisión, el Max Set Splitting, también llamado "Set Splitting" queda como sigue: dado un número entero k, ¿existe una partición de S que divida al menos k subconjuntos de F? Si k toma el valor de un parámetro dado, luego el "Set Splitting" posee complejidad parametrizada, es decir existe un algoritmo polinomial para cualquier valor de k.[3]
Referencias
Wikimedia foundation.
2010.
Mira otros diccionarios:
Problema abstracto — Saltar a navegación, búsqueda En ciencia computacional teórica, un problema abstracto o problema computacional es una relación entre un conjunto de instancias y un conjunto de soluciones. Un problema abstracto permite establecer formalmente la… … Wikipedia Español
Conjunto Gaitero "Saladillo de Nerio Matheus" (Los Auténticos Gaiteros del Pueblo) — Conjunto Gaitero El Saladillo de Nerio Matheus [[Archivo: |220px]] … Wikipedia Español
Problema de Molyneux — Saltar a navegación, búsqueda Las cirugías de cataratas han permitido que ciegos de nacimiento recuperen la vista y, de paso, contrastar experimentalmente el problema de Molyneaux, aunque sin resultados concluyentes. El problema de Molyneux es un … Wikipedia Español
Algoritmo de la división — Se ha sugerido que Algoritmo de la división sea fusionado en este artículo o sección (discusión). Una vez que hayas realizado la fusión de artículos, pide la fusión de historiales aquí. En matemáticas, y más precisamente en la aritmética, la… … Wikipedia Español
Multiplexación por División de Frecuencias Ortogonales — La Multiplexación por División de Frecuencias Ortogonales, en inglés Orthogonal Frequency Division Multiplexing (OFDM), o Discrete Multi tone Modulation (DMT) es una multiplexación que consiste en enviar un conjunto de ondas portadoras de… … Wikipedia Español
Modulación por división ortogonal de frecuencia — La modulación por división ortogonal de frecuencia, en inglés Orthogonal Frequency Division Multiplexing (OFDM), también llamada modulación por multitono discreto, en inglés Discreet Multitone Modulation (DMT), es una modulación que consiste en… … Enciclopedia Universal
Reino visigodo de Toledo — Este artículo o sección necesita una revisión de ortografía y gramática. Puedes colaborar editándolo (lee aquí sugerencias para mejorar tu ortografía). Cuando se haya corregido, borra este aviso por favor. Para otros usos de este térmi … Wikipedia Español
Programación dinámica (informática) — Saltar a navegación, búsqueda En informática, la programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas, como se describe a continuación … Wikipedia Español
Diego López de Zúñiga y Velasco — IV Conde de Nieva Nacimiento ¿1500? Burgos Fallecimiento 19 de febrero de 1564 (64 años) … Wikipedia Español
Emmy Noether — Amalie Emmy Noether Nacimiento 23 de marzo de 1882 Erlangen, Baviera, Alemania Fallecimiento … Wikipedia Español
