Réduction d'un problème de partition à 3 à un problème de partition équilibrée

Le problème 3-Partition demande si un ensemble de entiers peut être partitionné en ensembles de trois nombres entiers tels que chacun des montants mis en place pour un certain nombre entier donné . Le problème de partition équilibrée demande si entiers peuvent être partitionnés en deux ensembles de cardinalité égaux de sorte que les deux ensembles ont la même somme. Les deux problèmes sont connus pour être NP-complets. Cependant, 3-Partition est fortement NP-complet. Je n'ai vu dans la littérature aucune réduction de 3-Partition à Balanced Partition.$3n$$n$$B$$2n$

Je recherche une réduction (simple) du problème des 3 partitions au problème des partitions équilibrées.

Il existe des milliers de problèmes NP-complets dans la littérature, et la plupart des paires n'ont pas de réductions explicites. Étant donné que plusieurs réductions en temps polynomial se composent, il suffit aux chercheurs de s'arrêter lorsque le graphique des réductions publiées est fortement connecté, ce qui fait de la recherche sur l'exhaustivité des NP une activité beaucoup plus évolutive.

Bien que je ne vois vraiment pas l'intérêt, je vais vous faire plaisir en donnant une réduction raisonnablement simple de 3 PARTITIONS à PARTITION ÉQUILIBRÉE, avec quelques conseils sur le déroulement de la preuve de correction.

Soit l'entrée à la réduction soit , une instance de 3-PARTITION. Vérifiez que Σ i ∈ [ 3 n ] x i = n B . Soit β un grand nombre à choisir ultérieurement. Pour chaque i ∈ [ 3 n ] et chaque j ∈ [ n ] , sortir deux nombres x i β j + β n $x_1, \ldots, x_{3n}, B \in \mathbb Z$$\sum_{i\in[3n]} x_i = nB$$\beta$$i \in [3n]$$j \in [n]$ Intuitivement, le premier nombre signifie que x i est affecté à 3 partitions j , et le deuxième nombre signifie le contraire. Le terme x i β j est utilisé pour suivre la somme de 3 partitions j . Le terme β n + j est utilisé pour suivre la cardinalité de 3 partitions j . Le terme β 2 n + i est utilisé pour s'assurer que chaque x i est attribué exactement une fois. Le β

$$x_i \beta^j + \beta^{n+j} + \beta^{2n+i} + \beta^{(i+4)n+j}\\ \beta^{(i+4)n+j}.$$ $x_i$$j$$x_i \beta^j$$j$$\beta^{n+j}$$j$$\beta^{2n+i}$$x_i$ terme n + j est utilisé pour forcer ces nombres dans différentes partitions équilibrées.$\beta^{(i+4)n+j}$

Afficher deux autres nombres Le premier nombre identifie sa partition équilibrée comme "vrai", et l'autre, comme "faux". Leterme 1 est utilisé pour forcer ces nombres dans différentes partitions équilibrées. Les autres termes font la différence entre la somme d'une partition à 3 et la somme de son complément et la taille d'une partition à 3 et la taille de son complément et le nombre de fois où x i est attribué.

$$1 + \sum_{j\in[n]} \Bigl((n-2)B\beta^j + (3n-6)\beta^{n+j}\Bigr) + \sum_{i\in[3n]} (n-2)\beta^{2n+i}\\ 1.$$ $1$$x_i$

doit être choisi suffisamment grand pour éviter tout «débordement».$\beta$

Ce document, Fast Balanced Partitioning is Hard even on Grids and Trees , par Andreas Emil Feldmann contient ce que vous voulez! Bonne chance!

$k$