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...

Improve this question
$\endgroup$
2
  • 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$
    – user13756
    Commented Jul 25, 2013 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
    Commented Jul 25, 2013 at 12:20

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.