Partição de um conjunto de números inteiros em subconjuntos com somas prescritas

Eu vi esse problema:

Uma sequência não crescente de números inteiros positivos é n-realizável se o conjunto puder ser particionado em subconjuntos mutuamente separados 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$

no artigo "PARTIÇÃO DE UM CONJUNTO DE INTEGRANTES EM SUBJEITOS COM SOMAS PRESCRITOS", de Fu-Long Chen, Hung-Lin Fu, Yiju Wang e Jianqin Zhou

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

Eles resolveram o problema sob certas restrições. Mas não consigo encontrar nada sobre sua complexidade em geral. Alguém conhece uma referência sobre a complexidade desse problema? Isso me lembra o problema de empacotar caixas ou, em certo sentido, é semelhante ao problema de soma de subconjuntos. Então, eu acho que deve ser NP-completo em geral?

Mais precisamente, gosto de provar a completude do NP para o valor fixo de , por exemplo, quando ? Nesse caso, é muito semelhante ao problema de empacotar lixeira ou mochila, mas como queremos a igualdade, é diferente. Talvez haja variações desses problemas que correspondam à minha pergunta? $k$ $k = 3, 4, \ldots$

cc.complexity-theory user24175
fonte

Eu ficaria muito surpreso se esse problema fosse NP-completo.

Domotorp 28/02

@ user24175 Sabe-se que o tempo polinomial é solucionável se todo tiver cardinalidade 2?

S_{i}

$S_i$

Mohammad Al-Turkistany 01/03

@mohammad Se todo tiver cardinalidade , podemos reduzir o problema para a correspondência bipartida da seguinte maneira. Considere vértices, rotulados de a . Há uma vantagem entre vértice e vértice se houver um valor de tal forma 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 Isso está incorreto. Precisamos encontrar uma correspondência perfeita restrita com alguns ( ). Se queremos uma correspondência perfeita, então o problema é solucionável no tempo polinomial. Então, o problema provavelmente é -completo mesmo que cada tem cardinalidade 2.

\sum m_{i}

$\sum m_i$

N P

$NP$

S_{i}

$S_i$

Mohammad Al-Turkistany

@mohammad Não é , mas sim .

\sum m_{i}

$\sum m_i$

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

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

31515 S. Pek

Respostas:

Para qualquer fixo , não está em P, pela programação dinâmica? $k$

Para cada e modo que cada , defina para ser verdade sse é -realizable. Existem desses subproblemas (assumindo WLOG que ) e você tem uma recorrência como $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)$ $(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
fonte

Esse problema é conhecido por ser NP-completo no sentido forte. Veja, por exemplo,
/cstheory/709/cutting-sticks-puzzle/713

Gamow
fonte

@ Gamow: Muito obrigado. Mas, na verdade, eu tinha a prova de que eles sugeriram, por redução do problema de partição em vez do problema de 3 partições, um argumento bastante semelhante. Na verdade, estou procurando uma prova que possa ser aplicada a qualquer valor fixo de (o número de paus), por exemplo, quando ? Após a prova nessa página, para atingir o NP-completo para , temos que configurar, e , que não satisfaz as condições para o problema de 3 partições e, de fato, é uma instância muito especial do problema!

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$

user24175