Partición de un conjunto de enteros en subconjuntos con sumas prescritas

Vi este problema:

Se dice que una secuencia no creciente de enteros positivos es n-realizable si el conjunto puede dividirse en subconjuntos mutuamente disjuntos tal que para cada . $m_1,m_2,..., m_k$ $I_n=\{1,2,..., n\}$ $k$ $S_1,S_2,...,S_k$ $\sum_{x\in S_i} x = m_i$ $1\leq i \leq k$

en el documento "PARTICIÓN DE UN CONJUNTO DE INTEGRADORES EN SUBSETES CON SUMOS RECETADOS", por Fu-Long Chen, Hung-Lin Fu, Yiju Wang y Jianqin Zhou

http://journal.taiwanmathsoc.org.tw/index.php/TJM/article/view/1028

Han resuelto el problema bajo ciertas restricciones. Pero no puedo encontrar nada sobre su complejidad en general. ¿Alguien sabe una referencia sobre la complejidad de este problema? Me recuerda el problema del embalaje de la papelera o, en cierto sentido, es similar al problema de la suma de subconjuntos. Entonces, supongo que debe ser NP-complete en general.

Más precisamente, me gusta demostrar la integridad de NP para el valor fijo de , por ejemplo, cuando ? En este caso, es muy similar al problema del embalaje o la mochila, pero como queremos la igualdad, es diferente. ¿Quizás hay variaciones de estos problemas que coinciden con mi pregunta? $k$ $k = 3, 4, \ldots$

cc.complexity-theory usuario24175
fuente

Me sorprendería mucho si este problema fuera NP-completo.

domotorp

@ user24175 ¿Se sabe que puede resolverse en tiempo polinómico si cada

S_{i}

$S_i$ tiene cardinalidad 2?

Mohammad Al-Turkistany

@mohammad Si cada

tiene cardinalidad

, entonces podemos reducir el problema a la coincidencia bipartita de la siguiente manera. Considere

vértices, etiquetados de

. Hay un borde entre el vértice

y el vértice

si hay un valor

tal que

S_{i}

$S_i$

2

$2$

n

$n$

1

$1$

n

$n$

i

$i$

j

$j$

t

$t$

i + j = m_{t}

$i + j = m_t$

S. Pek

@ S.Pek Eso es incorrecto. Necesitamos encontrar una coincidencia perfecta restringida con algunos (

) Si queremos una coincidencia perfecta, entonces el problema es solucionable en el tiempo polinómico. Entonces, el problema probablemente es

-completo incluso si cada

tiene cardinalidad 2.

\sum m_{i}

$\sum m_i$

N P

$NP$

S_{i}

$S_i$

Mohammad Al-Turkistany

@mohammad No es

, sino más bien

\sum m_{i}

$\sum m_i$

\sum_{x \in S_{i}} x = m_{i}

$\sum_{x \in S_i} x = m_i$

S. Pek

Respuestas:

Para cualquier fija , ¿no está en P, mediante programación dinámica? $k$

Para cada y tal que cada , defina como verdadero iff $i\in\{0,\ldots,n\}$ $t_1, t_2, ..., t_k$ $t_i \in \{0,\ldots,m_i\}$ $S(i, t_1, t_2, \ldots, t_k)$ es -realizable. Luego están tales subproblemas (suponiendo WLOG que ), y tiene una recurrencia como $(t_1, t_2, .., t_k)$ $i$ $O(n^{2k+1})$ $\max_i m_i\le n^2$

$S(i, t_1, t_2, \ldots, t_k)$

$~ = S(i-1, t_1 - i, t_2, \ldots, t_k)$

$~\vee~ S(i-1, t_1, t_2 - i, t_3, \ldots, t_k)$

$~\vee~ \cdots$

$~\vee~ S(i-1, t_1, t_2 , t_3, \ldots, t_{k-1}, t_k- i)?$

Neal Young
fuente

Se sabe que este problema es NP-completo en el sentido fuerte. Ver por ejemplo
/cstheory/709/cutting-sticks-puzzle/713

Gamow
fuente

@ Gamow: Muchas gracias. Pero en realidad tenía la prueba de que sugirieron, por reducción del problema de partición en lugar del problema de 3 particiones, un argumento bastante similar. De hecho, estoy buscando una prueba que se pueda aplicar a cualquier valor fijo de

(el número de barras), por ejemplo, cuando

? Después de la prueba en esa página, para lograr la NP-completitud para

, tenemos que configurar,

, y

k

$k$

k = 3

$k=3$

k = 3

$k=3$

a_{1} = 1, \dots, a_{3 n} = N

$a_1=1,\ldots,a_{3n}=N$

n = 3

$n=3$ , que no satisface las condiciones para el problema de 3 particiones, y de hecho es una instancia muy especial del problema.

user24175