The shortest common nonsubsequence problem is NP-complete (Q1208726)

The shortest common nonsubsequence (SCNS) problem is: Given a finite set \(L\) of strings over an alphabet \(\Sigma\) and an integer \(k\in\mathbb{N}\), is there a string of length \(\leq k\) over \(\Sigma\) that is not a subsequence of any string in \(L\)? The SNCS problem is shown to be NP-complete for strings over an alphabet of size \(\geq 2\).