Does anyone know how to prove that Shortest Common String Problem is NP? I can provide a proof that it is NP-hard but I don't know how to prove SCSS in NP.
Asked
Active
Viewed 85 times
-1
-
Wouldn't the shortest common (sub)string typically be of length one? – Barry Cipra Dec 17 '17 at 23:44
1 Answers
0
Problems in NP are decision problems, not optimization problems. I would suggest formulating the Common Substring Problem as follows:
Instance: Let $\omega_{1}, \omega_{2} \in \Sigma^{*}$, and let $k \in \mathbb{Z}^{+}$.
Decision: Does there exist a string $\gamma$ of length at most $k$ s.t. $\gamma$ is a substring of both $\omega_{1}, \omega_{2}$?
Now such a string $\gamma$ is your certificate. Can you verify in polynomial time that $\gamma$ is a substring of both $\omega_{1}, \omega_{2}$ and $|\gamma| \leq k$?
ml0105
- 14,674