3 ms·

Is this not kind of trivial, at least the way they've defined it? It's kind of very obviously NP complete to me. Any of these text problems where you're tying t

Is this not kind of trivial, at least the way they've defined it? It's kind of very obviously NP complete to me. Any of these text problems where you're tying to optimize over a whole corpus is kind of not hard to see to be NP-complete, similar to longest common subsequence.

HeliumHydride 2y ago
Longest common substring is linear time.
- terrabiped 2y ago
  You may have misread the parent comment. Longest common substring is not the same type of problem as longest common subsequence.
  - Xmd5a 2y ago
    For those who were wondering what this means: common substring: contiguous common subsequence: not necessarily contiguous but in order
  - akoboldfrying 2y ago
    The post you responded to is merely giving evidence that the GP's overall claim "Any of these text problems where you're tying to optimize over a whole corpus is kind of not hard to see to be NP-complete" is sometimes not true in surprising ways -- Knuth conjectured that there was no linear time algorithm for longest common substring (but then suffix trees came along).
saiajc 2y ago
Longest common subsequence can be solved in at most quadratic time via dynamic programming.
- terrabiped 2y ago
  Longest common subsequence for an arbitrary input is NP-hard: https://en.wikipedia.org/wiki/Longest_common_subsequence https://en.wikipedia.org/wiki/Longest_common_subsequence Some narrow versions of it could be optimally solved with DP, but when the constraints are lifted, you will probably have to pay for it with either exponential memory or time. Same applies to the Knapsack problem. You can solve some variants of it with DP, but it won't generalize.
  - hexomancer 2y ago
    I wouldn't call the case with two sequence "some narrow version". It is by far the most common instance of the problem and honestly the first thing that pops into my mind when I hear LCS, that's why I was very surprised to hear it was NP-hard but it does make sense for an arbitrary number of sequences.

HeliumHydride 2y ago

Longest common substring is linear time.

terrabiped 2y ago
You may have misread the parent comment. Longest common substring is not the same type of problem as longest common subsequence.
- Xmd5a 2y ago
  For those who were wondering what this means: common substring: contiguous common subsequence: not necessarily contiguous but in order
- akoboldfrying 2y ago
  The post you responded to is merely giving evidence that the GP's overall claim "Any of these text problems where you're tying to optimize over a whole corpus is kind of not hard to see to be NP-complete" is sometimes not true in surprising ways -- Knuth conjectured that there was no linear time algorithm for longest common substring (but then suffix trees came along).

saiajc 2y ago

Longest common subsequence can be solved in at most quadratic time via dynamic programming.

terrabiped 2y ago
Longest common subsequence for an arbitrary input is NP-hard: https://en.wikipedia.org/wiki/Longest_common_subsequence https://en.wikipedia.org/wiki/Longest_common_subsequence Some narrow versions of it could be optimally solved with DP, but when the constraints are lifted, you will probably have to pay for it with either exponential memory or time. Same applies to the Knapsack problem. You can solve some variants of it with DP, but it won't generalize.
- hexomancer 2y ago
  I wouldn't call the case with two sequence "some narrow version". It is by far the most common instance of the problem and honestly the first thing that pops into my mind when I hear LCS, that's why I was very surprised to hear it was NP-hard but it does make sense for an arbitrary number of sequences.