np图同构

Question

我知道图同构应该在多项式时间内验证，但我对如何处理这个问题有点困惑。任何方向都将不胜感激。How can i show that a graph Isomorphism is in NP.

Answer 1

您可以通过给出解决图同构的多项式时间非确定性算法或通过给出多项式时间确定性算法检查用于图同构的证书确实是用于图同构的证书来显示这一点。

证明存在一个多项式时间的确定性证书检查算法应该不会太复杂。此问题的证书将是从一个图到另一个图的节点的映射。因此，您可以检查是否所有的边也被正确映射，节点的映射是否是双射的，等等。