3 ms·
Adventures in Programming Interviews: Misleadingly Simple NP-Hard Problem
- visarga 9y agoWe start from a set of people who sum their loans/debts up to zero. I think the problem reduces to finding subsets of people who sum up to zero, then solved recursively for each subset. If there are no subsets, then it requires n-1 payments. Finding the subsets could be solved with dynamic programming, so it's not NP-hard. http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/ http://www.geeksforgeeks.org/dynamic-programming-subset-sum-...
- tomsmeding 9y agoThe 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.