graph - 当被问及两张图是否相同时，问题是 P、NP、NP-hard、NP-complete 吗？

Question

我收到了一个问题，其中给出了两个图表，问题询问这两个图表是否相同，以及问题是 P、NP、NP-hard 还是 NP-complete。通过查看这两个图表，这些图表并不相同。但是，我不知道这是什么类型的问题。

标签： graphcomputation-theorynpnp-completenp-hard

Answer 1

首先，您必须定义“相同”的含义。有几种定义相等的方法，但在这种情况下最可能的一种是图同构，如果两个图之间存在保边双射，则两个图相等。

接下来，如果问题只是要确定您的两个给定图是否相同（这就是您所说的），那么问题在 O(1) 中是微不足道的（因此在 P 和 NP 中）。

但是，如果问题是要确定任何两个图是否同构，则问题在于 NP。目前既不知道它是否在 P 中，也不知道它是否是 NP 完全的。