The shortest common nonsubsequence problem is NP-complete (Q1208726)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The shortest common nonsubsequence problem is NP-complete |
scientific article; zbMATH DE number 166971
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The shortest common nonsubsequence problem is NP-complete |
scientific article; zbMATH DE number 166971 |
Statements
The shortest common nonsubsequence problem is NP-complete (English)
0 references
16 May 1993
0 references
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\).
0 references
combinatorial optimization
0 references
NP-completeness
0 references
strings
0 references
0.85635865
0 references
0 references
0.8328813
0 references
0.83181757
0 references
0 references
0.82906955
0 references
