Summing Triples problem is strongly $NP$-complete as shown by McDiarmid.

Summing Triples problem:

Input: list of 3N distinct positive integers

Question: Is there a partition of the list into N triples $(a_i, b_i, c_i)$ such that $a_i + b_i= c_i$ for each triple $i$?

The condition that all numbers must be distinct makes the problem interesting and McDiarmid calls it a surprisingly troublesome .

If the input is a multiset of positive integers, What is the complexity of Summing Triples? Does it remain NP-complete?

May be I overlooked an easy reduction from the original problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.