Closed. This question is off-topic. It is not currently accepting answers. Learn more。
想改进这个问题吗Update the question所以堆栈溢出的值小于aa>。
我知道图同构应该在多项式时间内得到验证，但我对如何处理这个问题有点困惑如有任何指示，将不胜感激。How can i show that a graph Isomorphism is in NP.
最佳答案
可以通过给出求解图同构的多项式时间不确定算法，或者通过给出多项式时间确定算法来检查图同构的证书是否确实是图同构的证书来说明这一点。
表明存在多项式时间确定性证书检查算法不应太复杂。此问题的证书将是节点从一个图到另一个图的节点的映射。所以你可以检查是否所有的边都被正确的映射，节点的映射是否是双射的，等等。。。
08-25 07:54