np-complete - 当 NP Complete 变成 NP hard

Question

一般来说，假设我们有一个NPC问题。给它增加更多的约束（让它更困难），这个问题有可能变成 NPH 吗？我知道 NPC 和 NPH 之间的区别，但我不知道如何证明向现有 NPC 问题添加新约束会使其成为 NPH 还是仍然是 NPC？

Answer 1

当然，额外的约束可以将 NPC 转换为 NPH 问题。此外，世界上没有人能够证明这一点。