3-partition problem
http://dbpedia.org/resource/3-partition_problem an entity of type: WikicatNP-completeProblems
The 3-partition problem is a strongly NP-complete problem in computer science. The problem is to decide whether a given multiset of integers can be partitioned into triplets that all have the same sum. More precisely:
* The input to the problem is a multiset S of n = 3 m positive integers. The sum of all integers is .
* The output is whether or not there exists a partition of S into m triplets S1, S2, …, Sm such that the sum of the numbers in each one is equal to T. The S1, S2, …, Sm must form a partition of S in the sense that they are disjoint and they cover S.
rdf:langString
En ciencias de la computación, el Problema de 3-partición es un problema NP-completo, que consiste en decidir si dado un multiconjunto S de n = 3m enteros positivos, puede ser particionado en m subconjuntos S1, S2, …, Sm tal que la suma de sus elementos sea la misma. Más precisamente, dado un multiconjunto S de 3m números enteros positivos, ¿puede S partirse en m subconjuntos S1, S2,..., Sm tal que la suma de los números de cada subconjunto sea igual?. Los subconjuntos S1,S2,..., Sm deben formar una partición de S en el sentido de que están disjuntos y cubren S.
rdf:langString
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 S1, S2, …, Sm tal que a soma dos números em cada subconjunto seja igual? Os subconjuntos S1, S2, …, Sm 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 Si, 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 Si é obrigado a conter exatamente três elemento
rdf:langString
rdf:langString
3-partition problem
rdf:langString
Problema de la 3-partición
rdf:langString
Problema das 3 Partições
xsd:integer
5253859
xsd:integer
1122256158
rdf:langString
The 3-partition problem is a strongly NP-complete problem in computer science. The problem is to decide whether a given multiset of integers can be partitioned into triplets that all have the same sum. More precisely:
* The input to the problem is a multiset S of n = 3 m positive integers. The sum of all integers is .
* The output is whether or not there exists a partition of S into m triplets S1, S2, …, Sm such that the sum of the numbers in each one is equal to T. The S1, S2, …, Sm must form a partition of S in the sense that they are disjoint and they cover S. The 3-partition problem remains strongly NP-complete under the restriction that every integer in S is strictly between T/4 and T/2.
rdf:langString
En ciencias de la computación, el Problema de 3-partición es un problema NP-completo, que consiste en decidir si dado un multiconjunto S de n = 3m enteros positivos, puede ser particionado en m subconjuntos S1, S2, …, Sm tal que la suma de sus elementos sea la misma. Más precisamente, dado un multiconjunto S de 3m números enteros positivos, ¿puede S partirse en m subconjuntos S1, S2,..., Sm tal que la suma de los números de cada subconjunto sea igual?. Los subconjuntos S1,S2,..., Sm deben formar una partición de S en el sentido de que están disjuntos y cubren S. Se puede definir la complejidad del problema de la siguiente manera: Sea B la suma buscada de cada subconjunto Si, o equivalentemente, sea mB la suma total de los números en S. Entonces el problema de la 3-Partición permanece dentro de NP-completo cuando cada entero de S está estrictamente entre B/2 y B/4. En este caso, cada subconjunto Si es forzado a ser un conjunto de 3 elementos ( una tripleta ). El problema de la 3-partición es similar al problema de la partición, que a su vez está relacionado con problema de la suma de subconjuntos. En el problema de la partición el objetivo es partir S subconjuntos que posean la misma suma. Es importante señalar que el problema de la 3-partición el objetivo es partir S en m subconjuntos (o n/3 subconjuntos), no 3 subconjuntos, con igual suma.
rdf:langString
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 S1, S2, …, Sm tal que a soma dos números em cada subconjunto seja igual? Os subconjuntos S1, S2, …, Sm 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 Si, 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 Si é 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.
xsd:nonNegativeInteger
10012