当NP完全变成NP难时

Question

一般来说，假设我们有一个NPC问题。添加更多的约束(使其更加困难)，问题有没有可能变成NPH？我知道NPC和NPH之间的区别，但我不知道如何证明在现有的NPC问题上添加新的约束会使其成为NPH，还是仍然是NPC？

Answer 1

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