Open Problem Garden - Subset-sums equality (pigeonhole version) - Comments

Re: A little more (re: Subset-sums equality (pigeonhole version))

kvanetten — Mon, 16 Jul 2007 06:18:07 +0200

Yes, I made that comment before I read the paper by Bazgan, Santha and Tuza. They mentioned in passing that the problem isn't NP-hard unless NP = coNP, and apparently felt that it was obvious enough to not require any further comment. I'm probably missing something obvious, but I can't quite follow this. With factorization (for example), a number's prime decomposition is unique and can serve as a certificate for both 'yes' and 'no' instances. For pigeonhole subset-sums equality, the solutions are not necessarily unique. It would depend on exactly how one crafted the corresponding decision problem, but it's not clear to me what the certificate would be for a 'no' instance.

Re: A little more (re: Subset-sums equality (pigeonhole version))

Anonymous — Sun, 15 Jul 2007 10:03:25 +0200

Problems with guaranteed-to-exist solutions (like this one, & others in PPA, PPAD, etc.) are not NP-complete unless NP = coNP and the Polynomial Hierarchy collapses. Now, we don't yet know that P != NP, or even that P != PH.

The problems are in PPP and PPA, respectively (re: Subset-sums equality (pigeonhole version))

Anonymous — Fri, 13 Jul 2007 09:10:47 +0200

Both this problem and the Smith/2nd Hamiltonian Path problems were suggested by Papadimitriou in his 1991 paper 'On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence". (See http://www.cs.berkeley.edu/~christos/papers/ for a copy of the journal version.)

These problems are in natural complexity classes related to though apparently somewhat larger than PPAD . The subset sum problem is in the class PPP and the Smith problem is in the class PPA. Neither is known to be complete for the respective complexity class as far as I know.

How's this? (re: Subset-sums equality (pigeonhole version))

mdevos — Mon, 09 Jul 2007 20:55:00 +0200

I am quite certian I have seen this problem called simply "subset-sums equality" before, so I have just appended "(pigeonhole version)" to the title. I hope that this is increasing the clarity.

You're right (re: Subset-sums equality (pigeonhole version))

kvanetten — Mon, 09 Jul 2007 06:55:16 +0200

I finally located a copy of the paper on the author's web page at http://www.lri.fr/~santha/ (why didn't that occur to me before?), and it's much clearer to me now--you're absolutely right. I guess the one suggestion I would make is to adopt their terminology and include the term 'pigeonhole' in the name of the problem to distinguish this variation from the more general case.

I think it is still open (re: Subset-sums equality (pigeonhole version))

mdevos — Mon, 09 Jul 2007 05:07:10 +0200

First a disclaimer: I am no expert on this problem.. I heard it awhile ago, liked it, wrote it down, and that's what you see here. However, I do believe it is still open. If my understanding is correct, the problem considered in the paper you mention ("Efficient approximation algorithms for the subset-sums equality problem" by Bazgan, Santha and Tuza, JCSS Vol.64 Issue 2, March 2002) is a relaxed version of the one stated here where the restriction is not present, and the goal is to find a pair of nonempty disjoint subsets so that and are as close as possible. I believe the only hardness results they obtain are for this problem.

The thing still missing is what to do with the funny assumption . Although the problem is a search problem which looks roughly like a knapsack-type problem (and thus should be NP-hard), the associated decision problem is trivially "true", yet there is no obvious way to use this information.

PS: thanks for the post!

A little more (re: Subset-sums equality (pigeonhole version))

kvanetten — Sun, 08 Jul 2007 15:55:04 +0200

Just an afterthought to my previous comment... Even if this problem is known not to be computable in polynomial time, it would still be interesting to know if it is NP-hard or not.

Should this problem still be considered open? (re: Subset-sums equality (pigeonhole version))

kvanetten — Sun, 08 Jul 2007 03:38:18 +0200

I was doing a quick search for background on this question and came across this article: http://dx.doi.org/10.1006/jcss.2001.1784 , "Efficient approximation algorithms for the subset-sums equality problem" by Bazgan, Santha and Tuza, JCSS Vol.64 Issue 2 (March 2002). I only have access to the abstract, so I might be misinterpreting this, but they say, "... On the other hand, we show that in the case where the value of a solution is the positive difference between the two partial sums, the problem is not 2nk -approximable in polynomial time unless P = NP, for any constant k." I take this to mean that there are no exact polynomial time algorithms unless P=NP. If so, this problem is only open in the sense that any question reducible to P vs. NP can be considered open.

Thanks! (re: Subset-sums equality (pigeonhole version))

mdevos — Mon, 02 Jul 2007 18:11:32 +0200

Thanks for your comment, I will edit the problerm and correct it.

Problem formulation (re: Subset-sums equality (pigeonhole version))

Anonymous — Sat, 30 Jun 2007 07:49:21 +0200

It seems to me that there are some typos in the problem formulation. The sum should be less than . The subsets should be nonempty.

- JS

Subset-sums equality (pigeonhole version)

mdevos — Sun, 18 Mar 2007 18:03:09 +0100

Author(s):

Subject: Theoretical Comp. Sci. » Complexity

Problem Let be natural numbers with . It follows from the pigeon-hole principle that there exist distinct subsets with . Is it possible to find such a pair in polynomial time?