6 ms·
The site you linked mentions: > The above solution may try all subsets of given set in worst case. Therefore time complexity of the above solution is exponenti
by tomsmeding 9y ago
The site you linked mentions:
> The above solution may try all subsets of given set in worst case. Therefore time complexity of the above solution is exponential. The problem is in-fact NP-Complete (There is no known polynomial time solution for this problem).
That contradicts your statement, since any NP-complete problem is by definition NP-hard.
- visarga 9y agoYes, you're right. NP-complete. My mistake This arXiv paper shows the STOA from 2015: https://arxiv.org/pdf/1507.02318.pdf https://arxiv.org/pdf/1507.02318.pdf It works in pseudopolynomial time. I read that it's quite an important problem, related to graphs and encryption.