Talk:3-partition problem

Undefined terms and questionable notation in the early example

The early example uses the undefined terms "feasible", "3-partition", "solution". As the example is important to help readers understand the 3-partition problem, the example should not used undefined terms. It should stick to the simplest possible concepts as explained up to the point where the example is given.

For the same reasons, it's unclear why 50% of the examples need to cover the relatively obscure restriction that all integers in S are between T/4 and T/2. This restriction is just one of many possible restrictions that do or do not preserve NP-hardness. The fact that this particular restriction happens to preserve NP-completeness does not make it fundamental. The article needs to be made clear why this particular restriction is so important that it is in the first example, or removed from the example. The same applies to stating the restriction in the opening section.

Finally, again for the same reasons, I think that using set notation for multisets is questionable. The notation { a, b, ..., x } is standard for sets, and a set contains no duplicates. The example uses the same notation for a multiset. At a minimum this should be explained, but perhaps better is to use a different standard notation. For example, to state the problem, one does not have to use multisets - one could use a list, a tuple, or something else. Perhaps this is better than using a multiset. — Preceding unsigned comment added by 2601:600:877F:DD20:F995:62D8:6750:5649 (talk) 22:21, 28 December 2023 (UTC)

Untitled

I believe there is a mistake in this article. the 3-partition problem is about partitioning a multiset into three partition. the problem presented here is obviously not NPC, it is in fact P. you made my friend believe he proved P=NP :)

Nope. the problem is stated precisely like this in Garey&Johnson, problem SP15. The Wikipedia article just leaves out an additional constraint (all numbers between B/4 and B/2 where B is the desired weight of all the partitions), but this doesn't affect the hardness. 88.73.61.8 09:27, 1 July 2007 (UTC)

Contradiction in the definition

I read a paper about a reduction-proof to 3-PARTITION, where I thought I found a contradiction. Seeking out this article, to clarify it for me, I found the exact same contradiction:

"The problem is to decide whether a given multiset of integers can be partitioned into triples that all have the same sum." vs. "More precisely, given a multiset S of n=3m positive integers, can S be partitioned into m subsets S_1, S_2, …, S_m such that the sum of the numbers in each subset is equal? The subsets S_1, S_2, …, S_m must form a partition of S in the sense that they are disjoint and they cover S."

While the former seems to imply that all S_i must have the same size (namely three), the latter clearly does not. So, is {{5}, {1,1,1,1,1}} a valid partition of {5,1,1,1,1,1}, or not? We clearly have two subsets, the sum of numbers in each subset is equal and it is a partition - but there is simply no interpretation of "triple", that would make this a partition into triples.

The article defines two different problems, both of which are generalization of the problem known as SP15 in Garey&Johnson

The aricle is a mess. The second sentence says, that the set must be partitioned into triples (let's call this problem A). The third sentence, which ironically starts with "More precisely,", says that partitioning the set into m subsets (which may or may not be triples) is fine (let's call this problem B). These are two different problem statements. In fact Problem B is a generalization of problem A, and problem A is a generalizations of the problem listed unter SP15 in Garey&Johnson. Being generalization of SP15, both problems A and B are of course NP-complete. The original definition of SP15 states, however, that the total sum of elements is mB (where B is an integer) and that all element are between B/4 and B/2 (both bounds exclusive). Under this assumption about the elements, problems A, B, and SP15 are in fact identical, as each of the subsets must be a triple. Consider that the elements of each subset must have a sum of B. And all the element are too small to have only two of them and too big to have four of them in one subset.

Unrelated Example

I think the example is not one for 3-partition, it looks like 2-partition. — Preceding unsigned comment added by 141.83.146.131 (talk) 11:53, 21 November 2018 (UTC)

ABC Reduction

The reduction from ABC-partition to 3-partition is the other way around. It should be that given a 3-partiotion problem instance we turn it into an ABC-partition instance. 2A0D:6FC2:52F0:9E00:E324:13CF:DCCC:B5EA (talk) 10:23, 1 October 2023 (UTC)