3
$\begingroup$

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.

$\endgroup$

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.