<p>I believe the problem was shown to be NP-Hard, as opposed to NP-Complete.  I am not personally familiar with any proof of reducibility of SAT to LCS.  Such a proof is required for a problem to be regarded as NP-Complete.  NP-Complete essentially means that a given problem is at least as hard as SAT.  The reduction of a problem to SAT in P-time and P-space merely shows the problem is itself no harder the SAT.  The LCS problem has a P-time and P-space solution as an answer set problem.</p>

CC BY-SA 4.0
2019-06-25T20:53:02.617Z
To the 4 down voters: How dare you! This answer is excellent. User36160 says (very original name btw) "[got links]?" - use Google is my reply.
Alan Burstein
CC BY-SA 4.0
2022-05-20T13:27:17.777Z
It’s important to note that the LCSq between 2 strings is NP-Hard, when comparing 3 strings the problem is NP-Complete according to Wikipedia’s list of NP-Complete problems.
Alan Burstein
CC BY-SA 3.0
2016-01-03T03:16:26.750Z
2016-01-03T03:16:26.750Z
user36960
<p>This <a href="http://pagesperso.lina.univ-nantes.fr/~bulteau-l/pdf/BBJTV-cpm12.pdf">paper by Blin et al.</a> (Hardness of Longest Common Subsequence for Sequences with Bounded Run-Lengths, CPM'12) provides a reduction from independent set to LCS where the Hamming weights of all strings are the same (it is $n-1$ where $n$ is the number of vertices in the independent set instance). Thus, the problem remains NP-complete under this assumption.</p>

CC BY-SA 3.0
2015-07-13T07:21:07.467Z
Thanks for the answer. In this case the Hamming Weight (no. of 1's) are fixed to a constant M in each string. Assuming, both the number of 1's and 0's are fixed (i.e. the string sizes are same along with the Hamming Weight) does the LCS problem reduce to P ?
TheoryQuest1
CC BY-SA 3.0
2015-07-13T10:39:53.017Z
In the reduction by Blin et al., all of the strings have the same number of 0's and 1's.
JWM
CC BY-SA 3.0
2015-07-12T19:13:24.597Z
2015-07-12T19:13:24.597Z
JWM
<p>The general <a href="https://en.wikipedia.org/wiki/Longest_common_subsequence_problem" rel="nofollow">longest common subsequence problem</a> (LCS) over a binary alphabet is NP-complete. Does the problem remain NP-complete if each input string has <em>m</em> zeros and <em>n</em> ones, where <em>m</em> and <em>n</em> are constants?</p>

<p>I asked this question on <a href="https://cs.stackexchange.com/questions/44306/computational-complexity-of-longest-common-subsequence-problem-variation">cs.stackexchange</a> and was told, "The problem probably remains NP-complete." However, I was unsuccessful in showing a reduction from the original LCS problem.</p>

CC BY-SA 4.0
2024-05-14T18:08:14.230Z
Of course I guess $n$ and $m$ are "constants" in the sense that these values are the same for all input strings, not that they are fixed to be constants in the problem setting. (Otherwise of course the problem is no longer NP-complete given that the maximal length of the resulting longest common subsequence would also be bounded by a constant.)
Antoine Amarilli 'a3nm'
<cc.complexity-theory><np-hardness>
Is longest common subsequence with bounded occurrences NP-complete?
TheoryQuest1
# Is longest common subsequence with bounded occurrences NP-complete?

(Asked by: username_0 on 2015-07-12)

The general [longest common subsequence problem](https://en.wikipedia.org/wiki/Longest_common_subsequence_problem) (LCS) over a binary alphabet is NP-complete. Does the problem remain NP-complete if each input string has *m* zeros and *n* ones, where *m* and *n* are constants?

I asked this question on [cs.stackexchange](https://cs.stackexchange.com/questions/44306/computational-complexity-of-longest-common-subsequence-problem-variation) and was told, "The problem probably remains NP-complete." However, I was unsuccessful in showing a reduction from the original LCS problem.

**Tags:** cc.complexity-theory, np-hardness
> **Comments:**
> **username_1**: Of course I guess $n$ and $m$ are "constants" in the sense that these values are the same for all input strings, not that they are fixed to be constants in the problem setting. (Otherwise of course the problem is no longer NP-complete given that the maximal length of the resulting longest common subsequence would also be bounded by a constant.)  

---

## 2 answers

### Answer by username_4 on 2015-07-12. Score: 9 | Accepted answer

This [paper by Blin et al.](http://pagesperso.lina.univ-nantes.fr/~bulteau-l/pdf/BBJTV-cpm12.pdf) (Hardness of Longest Common Subsequence for Sequences with Bounded Run-Lengths, CPM'12) provides a reduction from independent set to LCS where the Hamming weights of all strings are the same (it is $n-1$ where $n$ is the number of vertices in the independent set instance). Thus, the problem remains NP-complete under this assumption.

> **Comments:**
> **username_0**: Thanks for the answer. In this case the Hamming Weight (no. of 1's) are fixed to a constant M in each string. Assuming, both the number of 1's and 0's are fixed (i.e. the string sizes are same along with the Hamming Weight) does the LCS problem reduce to P ?  
> **username_4**: In the reduction by Blin et al., all of the strings have the same number of 0's and 1's.  

---

### Answer by username_2 on 2016-01-03. Score: -3

I believe the problem was shown to be NP-Hard, as opposed to NP-Complete. I am not personally familiar with any proof of reducibility of SAT to LCS. Such a proof is required for a problem to be regarded as NP-Complete. NP-Complete essentially means that a given problem is at least as hard as SAT. The reduction of a problem to SAT in P-time and P-space merely shows the problem is itself no harder the SAT. The LCS problem has a P-time and P-space solution as an answer set problem.

> **Comments:**
> **username_3**: To the 4 down voters: How dare you! This answer is excellent. User36160 says (very original name btw) "[got links]?" - use Google is my reply.  
> **username_3**: It’s important to note that the LCSq between 2 strings is NP-Hard, when comparing 3 strings the problem is NP-Complete according to Wikipedia’s list of NP-Complete problems.  

---

