当被问及两个图是否相同时，问题P，NP，NP难，NP完全吗

Question

我有一个问题，其中给出了两个图，问题询问这两个图是否相同，以及问题是p、NP、NP难还是NP完全。从这两张图来看，这两张图表并不相同。然而，我不知道这是什么类型的问题

Answer 1

首先，你必须定义你所说的"相同"；。有几种定义相等的方法，但在这种情况下最有可能的是图同构，其中如果两个图之间存在保边双射，则两个图相等。

接下来，如果问题只是决定你的两个给定的图是否相同(这就是你所说的(，那么问题在O(1(中是平凡的(因此在p和NP中也是如此(。

然而，如果问题是决定任何两个图是否同构，那么问题就在NP中。目前还不知道它是否在p中，也不知道它是NP完全的。