F.A.Qs | Home | ProblemSet | Status | Ranklist | Contest | Login | Register |
---|
Problem 5454 >> 现代科技这么发达了吗 |
tangjz @ 2018-11-16 03:01:44
https://www.sciencedirect.com/science/article/pii/030439759390200D
最短公共非子序列问题在字符集大小 >= 2 的时候好像一直是NP完全?这题能做? |
zbw001 @ 2018-11-16 13:48:40
这上面说的是给定L个序列吧
|
tangjz @ 2018-11-16 15:15:37
上面说的是:给定一个字符集 Σ,和在这个字符集上的字符串集合 L,以及一个非负整数 k,在这个字符集构成的字符串里,确定是否存在一个长度不超过 k 的字符串使得它不是任何一个 L 中字符串的子序列(子序列可以不连续),这个问题在字符集大小不小于 2 时是 NP 完全的。
|
zbw001 @ 2018-11-16 16:30:12
那大概是 |L| 个序列,指数上的可能是 |L|
|