求帮助：证明一个问题是NP问题

如何证明以下两个问题是NP问题呢？
1：给定一个图A，图A是强连通图？
2：给定一个图A，图A不是强连通图？
感谢！！！

你先确定你说的是NP而不是NP-complete或者NP-hard的。简单的办法：因为这两个问题都可以在polynomial time判定（参见求strongly connected component的Tarjan算法），所以是都P问题，P问题都是NP问题，所以它们都是NP问题。按照定义的办法：NP问题的一种等价定义是，给定这个问题的任何一个yes instance和对应的certificate，我可以在polynomial time验证这个certificate。你说的strongly connected component问题，certificate可以是一个tour，因为验证一个sequence of vertices是不是一个经过图上所有点的合法的tour可以在polynomial完成，所以是NP问题。