當NP完全變爲NP時

Question

一般來說，假設我們有一個NPC問題。給它增加更多的約束（使它更難），這個問題有可能成爲NPH嗎？我知道NPC和NPH之間的區別，但我不知道如何證明給現有的NPC增加新的限制會使它成爲NPH還是仍然是NPC？

Answer 1

當然可以通過附加約束將NPC轉換爲NPH問題。此外，世界上沒有人能夠證明這一點。