4 ms·

I skimmed through because it sounds fairly click-baity... From what I gather, they're claiming to have solved NP-complete problems to some degree with some abst

• ajb 8y ago
  The article doesn't even mention NP-completeness. Nor does the paper: https://arxiv.org/pdf/1804.06355.pdf https://arxiv.org/pdf/1804.06355.pdf Haven't read enough yet to comment otherwise, but let's not spread rumours.
• justinclift 8y ago
  The abstract seems to be comparing having to search an entire problem space for the most optimal result ("the current approach") with an approach using sampling for a good enough result?
• allenz 8y ago
  Submodular maximization is indeed NP-complete, but we can find approximate solutions in polynomial time. This paper speeds up the parallel running time of the approximation from O(n) to O(log n), meaning that they've found a way to make the algorithm more parallelizable, though you still have to do the same amount of work.
  • leetbulb 8y ago
    Got it! Thanks!