2
$\begingroup$

Who can be attributed with the discovery or invention of the unary subset sum algorithm which is known to have polynomial time complexity but exponential space complexity.

I am currently writing a research paper in which I would like to put proper attribution...

$\endgroup$
  • 1
    $\begingroup$ Hmm...are you sure Unary Subset Sum has exponential space complexity? I thought it is trivially in NL, and recently proved to be in L (by D. Kane), if I'm not mistaken. Unless, you are talking here about simultaneous Time-Space measures (and so should say this explicitly). $\endgroup$ – Dilworth Jul 25 '13 at 9:31
  • 1
    $\begingroup$ You're right about Kane's paper... But I wanted to know who had first discussed in the literature the version that is described in most papers on subset sum as the "unary subset-sum with exponential space complexity and polynomial time complexity". The first occurence that seems to be reported is Bellman (but his formulation of the problem is "bottleneck problems" and not the textbook "subset-sum" that everybody can read everywhere.... So I am not really sure... $\endgroup$ – Phil Jul 25 '13 at 12:20

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.