想问一下
同样在NPC的问题里, 都视为一样难吗?
那这样所有P里的问题也都视为一样难吗?
例如一个问题O(n)可解, 另一个O(n^2)可解
这样也视为一样难吗?

一样难是因为可以互相reduction在P里面谈reduce没有什么意义因为是规定多项式时间内可以转换但你解决的时间就是已经多项式时间了

以 polynomial-time reduction 的观点来看 NPC 都是一样难但是有不同的 reduction 定义 可以区分 NPC 问题的难度

感谢楼上算法大大，长知识惹

感谢F大 长知识了

感谢F大指正！

举例来说，我们可以用 Log-space reduction 来定义 NPChttps://en.wikipedia.org/wiki/Log-space_reduction有些书是用 log-space reduction 来定义 NPC但是 log-space reduction 和 polynomial-time reduction定义出来的 NPC 是不是等价 仍然是 open question