NP 完全或 NP 困难，在等价问题中？

Question

我运行进了一个问题

Finding of all cycle in a graph is NP-Complete.

我在 Google 搜索中看到了这条注释。

counting all cycle in a graph is NP-Complete.

are these two sentence equivalences ? can we say these two is NP-Hard?

感谢每一个有用的笔记。

Answer 1

are these two sentence equivalences ?

是的，但措辞不当。 None 这些问题是决策问题。决策问题 return 非真即假。 NP-Complete 是决策问题的分类，因此 "improper" 可以说以上是 NP-Complete。但是如果我们说，"Are there X number of cycles in a graph?" 那将是一个 NP 完全问题。

can we say these two is NP-Hard? 是的 NP-Hard 意味着它至少和 NP 一样难，因为这两个问题是 NP-Complete 那么这是真的。