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?
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.Sign up to join this community
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.