Каждый NP-полный проб. признать ограничение полиномиального времени?
Я должен ответить на этот вопрос как домашнее задание, но я нахожу очень мало материала для работы. Я понимаю, что такое NP-полная проблема и что такое ограничение. На мой взгляд, это утверждение верно, потому что вы всегда можете ограничить проблему, чтобы "облегчить проблему". Но я смотрю на это с высоты птичьего полета... Может ли кто-нибудь помочь мне добиться прогресса в поиске ответа на этот вопрос? Любая помощь будет высоко ценится.
1 ответ
Преобразование моего комментария в ответ - рассмотрим "пустую проблему", проблему, набор экземпляров которой пуст. Поскольку пустой набор является подмножеством каждого набора, технически эта проблема считается ограничением любого языка (включая языки, не входящие в NP). Это также проблема в P; Вы можете построить TM полиномиального времени, которая всегда отклоняет его ввод. Поэтому каждая задача в NP имеет ограничение по полиномиальному времени.
Однако мне все еще интересно, имеет ли каждая проблема NP, набор экземпляров которой бесконечен, ограничение по полиномиальному времени, набор экземпляров которого также бесконечен. Это более интересный вопрос, ИМХО, и у меня нет ответа.
Надеюсь это поможет!