| dbo:abstract
|
- 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. (en)
- 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. (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 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. (pt)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 10012 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- 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. (en)
- 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. (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 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 (pt)
|
| rdfs:label
|
- 3-partition problem (en)
- Problema de la 3-partición (es)
- Problema das 3 Partições (pt)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
