1
$\begingroup$

Is the problem to construct a $\mathcal{O}\mbox{*}(1.4^n)$ (or better) time algorithm for subset sum still open? I wanted to check the problem before finishing a paper.

The most recent reference I found to this open problem is on next paper:

'SETH-Based Lower Bounds for Subset Sum and Bicriteria Path, Amir Abboud et al.' 2017 link

citing:

'Open problems around exact algorithms, Woeginger' 2008 link.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ It's probably still open. If not, you would probably find out about it in your literature search. $\endgroup$ – Yuval Filmus Sep 25 '18 at 5:29
  • $\begingroup$ found another paper, from May/18 stating is still open, so I'll assume is open and move forward, thanks! $\endgroup$ – Jesus Salas Sep 25 '18 at 23:50
  • $\begingroup$ People will cite your paper once published , "Yup, it is still open!". $\endgroup$ – John L. Sep 26 '18 at 19:43
2
$\begingroup$

The way to tell if it is open is to read more recent papers to see if any of them make progress. If not, it's still open. The way to find more recent papers is to look up that paper on Google Scholar and look through all the papers that site it. If someone has made progress, it's likely they'll cite that paper.

In general, don't expect to necessarily find a paper somewhere that says "it's still open". People aren't necessarily going to bother repeating "yup, still open" every year.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.