Как правило, если у нас есть проблема с NPC. Добавляя к нему больше ограничений (усложняя), возможно ли, что проблема станет NPH? Я знаю разницу между NPC и NPH, но я не знаю, как показать, что добавление новых ограничений к существующей проблеме NPC сделает ее NPH или все еще останется NPC?
Когда NP завершено, становится NP сложно
Ответы (1)
Конечно, дополнительное ограничение может превратить NPC в проблему NPH. Кроме того, в Мире не могло быть человека, способного это доказать.
person
AlexWien
schedule
29.11.2012
Спасибо, Алекс. Вы знаете какой-нибудь документ или документы, подтверждающие это? Мне просто любопытно посмотреть.
- person Sara; 29.11.2012
извините, нет бумаги. но дополнительное ограничение можно рассматривать как новую проблему. Новую проблему может быть сложнее или проще решить.
- person AlexWien; 03.12.2012
