Shortest Common String Problem is NP

Question

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.

Answer 1

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$?