I was wondering if anybody knows if there is an algorithm for Subset-sum, preferably exact, having a $O(n)$ Time Complexity or near-linear ($n$ = number of elements in the input set)

I remember that some time ago I read a paper (from Psinger? I can't find it again..) stating that there is a linear or near-linear time complexity algorithm when the target value is bounded to a constant.

Can somebody explain to how this algorithm can achieve such TC when the target value is bounded to a constant?

  • $\begingroup$ You are claiming to have a solution for a well-known, difficult open problem. This is an extraordinary claim requiring extraordinary evidence. You have not provided such so there is not much to talk about. Even if you had, this would not be a good post for SE; it is not our goal here to make broad advances to science in a single post. See here for a related discussion. $\endgroup$ – Raphael Jan 6 '18 at 12:31
  • $\begingroup$ @Raphael I see your point, and I read the guidance you linked and can only agree that this question, although unintentionally, fits what I found there, I should have asked this in other way, so I'm going to keep the comment here for you to read and rephrase the question that was ill-formed. And as per your guidance SE should probably not be the right place for this. $\endgroup$ – John Seppard Jan 6 '18 at 18:32
  • 1
    $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$ – D.W. Jan 6 '18 at 18:54
  • $\begingroup$ You should clarify what "n" is. $\endgroup$ – Raphael Jan 6 '18 at 19:11

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.