0
$\begingroup$

Is there a formal proof of the worst-case configuration of the subset sum problem?

In other words - is there a set proven to be the hardest to find a subset equals to 0 from?

thanks

$\endgroup$
  • 3
    $\begingroup$ I don't understand your question. Are you asking for hardness of individual instances? If so, what do you mean by "hard"? In complexity theory usually infinite collections of instances are dealt with, because solutions to a finite number of instances can be added as a table to the recognizer. $\endgroup$ – András Salamon Oct 20 '10 at 15:34
  • 1
    $\begingroup$ Voting to close: too elementary, see the FAQ. $\endgroup$ – Jukka Suomela Oct 20 '10 at 15:35
  • $\begingroup$ Hi, I really think that having an open and free discussion with people in the "general public" will benefit the pursue of answering open questions, and by closing question which are "too simple" or dismissing them you are not helping the situation. $\endgroup$ – shul Oct 21 '10 at 14:02
  • $\begingroup$ This website is primarily for questions and answers, not for “open and free discussions.” If you really want to try to change the purpose of the website, you can start a thread on Meta, but I do not think that it is a good idea. $\endgroup$ – Tsuyoshi Ito Oct 23 '10 at 11:43
  • $\begingroup$ Ok Tsuyoshi, thank you for the clarification. I wonder if there is such a site (and if asking about such a site is in the realms of this site's "purpose") $\endgroup$ – shul Nov 12 '10 at 19:57
11
$\begingroup$

No, there isn't. If there was such a particular instance of subset sum problem that would be "the hardest" we could solve it by brute-force, and then hard-code it (and its answer) into our program solving subset sum problem. Then our algorithm, given an instance to solve, would first check whether the input matches that hard instance, and if so, it would simply output its answer in O(1) time - and thus, the instance wouldn't be hard anymore.

In general, hardness lies in the problems (which we can see as infinite sets of instances), and not in particular instances (or even some finite sets of instances), and searching for explicit instances of the problem that are "the hardest" doesn't make much sense. You could restate the question to ask about some "hard" family of instances - i.e., such families that our problem remains NP-hard when limited only to these instances. You could probably get one example of such families by looking at the details in the reduction showing that SUBSET-SUM in NP-hard.

Answer to the comment: Generally, this kind of questions is too elemental for this site - I would really advise you to read some good intro to complexity theory, or at least to do a DFS on wikipedia starting from this article: http://en.wikipedia.org/wiki/NP-complete I think you will find all your answers there. Then, if you're interested specifically in the SUBSET-SUM problem, you could look into the reduction showing its NP-hardness - you will see there arbitrary instances of SAT (or some other NP-hard problem) being mapped into some particular instances of SUBSET-SUM (the set of these "hard" instances will probably be smaller than the set of all instances, but still infinite and "dense"). And yes, if you can solve the SUBSET-SUM problem restricted to this set of instances, you will prove that P=NP.

$\endgroup$
  • $\begingroup$ Karolina, thanks, I didn't ask about a specific set, but that's ok. Can you give a layman's example of the rules needed for a set to be hard to solve? would showing that this kind of a set is not NP hard prove that P=NP or will that only be true to this subset? (and yes, I know everybody thinks P!=NP) $\endgroup$ – shul Oct 20 '10 at 21:27

Not the answer you're looking for? Browse other questions tagged or ask your own question.