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

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

CC BY-SA 3.0
2013-07-25T12:20:16.643Z
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...
Phil
<ho.history-overview>
Unary subset sum
Phil
# Unary subset sum

(Asked by: username_0 on 2013-07-25)

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

**Tags:** ho.history-overview

> **Comments:**
> **username_0**: 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...  

---

## 0 answers

