Complexidade computacional do problema de 3 partições com números distintos

23

Esta pergunta está relacionada a uma resposta que eu postei em resposta a outra pergunta.

O problema de 3 partições é o seguinte:
Instância : números inteiros positivos a 1 ,…, a n , em que n = 3m e a soma dos n números inteiros é igual a mB, de modo que cada a i satisfaça B / 4 <a i <B / 2.
Pergunta : Os números inteiros a 1 ,…, n podem ser particionados em m multisets para que a soma de cada multiset seja igual a B?

É sabido que o problema de 3 partições é NP-completo no forte sentido de que permanece NP-completo, mesmo que os números na entrada sejam dados unários. Veja Garey e Johnson para uma prova.

Perguntas : O problema de 3 partições permanece NP-completo se os números a 1 ,…, n são todos distintos? Permanece NP-completo no sentido forte?

(Meu sentimento é que as respostas para ambas as perguntas provavelmente são afirmativas, porque não vejo nenhuma razão para que o problema se torne mais fácil se todos os números forem distintos.)

Não parece que a prova de Garey e Johnson estabeleça a completude da NP dessa versão restrita.

Na resposta à outra pergunta vinculada acima, dei uma prova de que o problema de 6 partições (definido analogamente) com números distintos é NP-completo no sentido forte.

cc.complexity-theory np-hardness Tsuyoshi Ito
fonte
2
Eu acho que esse é um problema importante; Eu encontrei vários artigos na literatura que afirmam ou assumem que a versão do conjunto é difícil, sem justificativa melhor do que uma citação para a versão multiset em Garey e Johnson, e que usam essa suposição em uma reivindicação de completude da NP para algum outro problema .
David Eppstein

Respostas:

19

a1,…,anB/4<ai<B/2

[1]: Heather Hulett, Todd G. Will, Gerhard J. Woeginger: Realizações multigráficas de seqüências de graus: Maximização é fácil, minimização é difícil. Oper. Res. Lett. 36 (5): 594-596 (2008). DOI

Serge Gaspers
fonte
5
B/4<ai<B/2ai
1
De fato, é simples também impor esses limites.
Serge Gaspers
2
Obrigado, responde minha pergunta completamente. Observe que o problema parcial de completação de quadrados latinos pode ser facilmente formulado como um caso especial da correspondência tridimensional. Não me ocorreu substituir o 3DM pelo PLSC, mas depois de ver a prova, a abordagem parece bastante natural.
Tsuyoshi Ito