Problema das 3 Partições

O Problema das 3 Partições é um problema NP-completo na Ciência da Computação. O problema serve para decidir quando um dado multiconjunto de inteiros pode ser particionado em triplas onde todas têm a mesma soma. Mais precisamente, dado um multiconjunto S de n = 3m inteiros positivos, S pode ser particionado em m sunconjuntos S₁, S₂, …, S_m tal que a soma dos números em cada subconjunto seja igual? Os subconjuntos S₁, S₂, …, S_m devem formar uma partição de S de forma que eles sejam disjuntos e que eles cobrem S. Seja B a soma (desejada) de cada subconjunto S_i, ou equivalentemente, a soma total dos números em S ser m B. O problema das 3 partições é NP-completo pois cada inteiro de S está estritamente entre B/4 e B/2. Nesse caso, cada subconjunto S_i é obrigado a conter exatamente três elementos (uma tripla).

O problema das 3 partições é similar ao problema da partição, o qual está relacionado como o problema da soma dos subconjuntos. Nesse problema, o objetivo é particionar S em dois subconjuntos com somas iguais. No problema das 3 partições, o objetivo é de particionar S em m subconjuntos (ou n/3 subconjuntos), não apenas três subconjuntos, com a soma igual.

NP-Completude Forte

O problema das 3 partições permanece NP-Completo mesmo quando os números em S são delimitados por uma entrada polinomial n. Em outras palavras, o problema permanece NP-completo mesmo quando os números da entrada são representados em unário. i.e., o problema das 3 partições é NP-Completo Forte. Essa propriedade, e o problema das 3 partições em geral, é útil em várias reduções onde números são naturalmente representados em unário. Por outro lado, o problema da partição só é considerado NP-Completo quando os números são representados em binário e possuem valor exponencial n.

Descrições

Garey e Johnson (1975) provaram originalmente que o problema das 3 partições é NP-Completo a partir de uma redução do problema da compatibilidade tri-dimensional. A referência clássica de Garey e Johnson (1979) descreve uma prova de NP-Completude, reduzindo de compatibilidade tri-dimensional para 4 partições e, assim, para 3 partições. O Problema das 4 Partições é uma analogia ao problema das 3 partições, onde o objetivo é de particionar um dado conjunto S em quadras com a mesma soma: mais precisamente, a diferença é que S agora consiste de n = 4m números inteiros, cada um estritamente entre B/5 e B/3.

Referências

• Garey, Michael R. and David S. Johnson (1979), Computers and Intractability; A Guide to the Theory of NP-Completeness. ISBN 0-7167-1045-5. Pages 96–105 and 224.
• Garey, Michael R. and David S. Johnson (1975). «Complexity results for multiprocessor scheduling under resource constraints». SIAM Journal on Computing. 4 (4): 397–411. doi:10.1137/0204035