Aufteilung einer Menge von ganzen Zahlen in Teilmengen mit vorgeschriebenen Summen

Ich habe dieses Problem gesehen:

Eine nicht zunehmende Folge positiver Ganzzahlen $m_1,m_2,..., m_k$ gilt als n-realisierbar, wenn die Menge $I_n=\{1,2,..., n\}$ kann in $k$ voneinander getrennte Teilmengen $S_1,S_2,...,S_k$ so, dass $\sum_{x\in S_i} x = m_i$ für jede $1\leq i \leq k$ .

in der Arbeit "Teilung einer Reihe von Integern in Teilmengen mit vorgeschriebenen Summen" von Fu-Long Chen, Hung-Lin Fu, Yiju Wang und Jianqin Zhou

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

Sie haben das Problem unter bestimmten Bedingungen gelöst. Aber ich kann nichts über seine Komplexität im Allgemeinen finden. Kennt jemand eine Referenz über die Komplexität dieses Problems? Es erinnert mich an das Problem des Packens von Behältern oder ähnelt in gewissem Sinne dem Problem der Teilmengen-Summe. Also, ich denke, es muss im Allgemeinen NP-vollständig sein?

Genauer gesagt möchte ich die NP-Vollständigkeit für den festen Wert von beweisen $k$ , zum Beispiel wenn $k = 3, 4, \ldots$ ? In diesem Fall ist es dem Problem der Müllverpackung oder des Rucksacks sehr ähnlich, aber da wir die Gleichheit wollen, ist es anders. Vielleicht gibt es Variationen dieser Probleme, die meiner Frage entsprechen?

cc.complexity-theory user24175
quelle

Ich wäre sehr überrascht, wenn dieses Problem NP-vollständig wäre.

Domotorp

@ user24175 Ist bekannt, dass die Polynomzeit lösbar ist, wenn jedes

die Kardinalität 2 hat?

S_{i}

$S_i$

Mohammad Al-Turkistany

@mohammad Wenn jedes

Kardinalität

, können wir das Problem wie folgt auf eine zweiteilige Übereinstimmung reduzieren. Betrachten Sie

Eckpunkte mit den Bezeichnungen

bis

. Es gibt eine Kante zwischen dem Scheitelpunkt

und dem Scheitelpunkt

wenn es einen Wert

so dass

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 Das ist falsch. Wir müssen eine eingeschränkte perfekte Übereinstimmung mit bestimmten einigen finden (

). Wenn wir eine perfekte Übereinstimmung wollen, ist das Problem polynomial lösbar. Das Problem ist also wahrscheinlich

-vollständig, selbst wenn jedes

Kardinalität 2 hat.

\sum m_{i}

$\sum m_i$

N P

$NP$

S_{i}

$S_i$

Mohammad Al-Turkistany

@mohammad Es ist nicht

, sondern

\sum m_{i}

$\sum m_i$

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

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

S. Pek

Antworten:

Ist es für ein festes nicht in P durch dynamische Programmierung? $k$

Für jedes und , so dass jedes , definieren , wahr zu sein 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)$ $(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
quelle

Es ist bekannt, dass dieses Problem im starken Sinne NP-vollständig ist. Siehe zum Beispiel
/cstheory/709/cutting-sticks-puzzle/713

Gamow
quelle

@ Gamow: Vielen Dank. Aber ich hatte tatsächlich den Beweis, dass sie durch Reduktion des Partitionsproblems anstelle des 3-Partitionsproblems ein ziemlich ähnliches Argument vorschlugen. Ich suche tatsächlich nach einem Beweis, der auf jeden festen Wert von (die Anzahl der Sticks) angewendet werden kann , zum Beispiel wenn ? Um die NP-Vollständigkeit für , müssen wir nach dem Beweis auf dieser Seite und einrichten , was die Bedingungen für nicht erfüllt das 3-Partitions-Problem, und in der Tat ist es eine ganz besondere Instanz des Problems!

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