2

假设 P = NP，这是否意味着哈密顿循环不再是 NP-Hard？Hamiltonian-Cycle 是一种语言，其中给定的图 G 包含一个 Ham-Cycle。

4

1 回答 1

1

NP-Hard 的定义是它允许您解决一个 NP 完全问题，这是一种奇特的说法，即“解决这个问题至少与解决任何 NP 问题一样难”。

如果 P = NP，则 NP-hard 问题保持 NP-hard，即“解决这个问题仍然至少与解决任何 NP 问题一样难”。但是由于 P = NP，这相当于“解决这个问题至少和解决任何 P 问题一样难”。这通常不被认为是困难的

于 2021-12-16T00:15:58.937 回答