Я должен ответить на этот вопрос в качестве домашнего задания, но я нахожу очень мало материала для работы. Я понимаю, что такое NP-полная задача и что такое ограничение. На мой взгляд, это утверждение верно, потому что всегда можно ограничить задачу, чтобы «облегчить задачу». Но я смотрю на это с высоты птичьего полета... Может ли кто-нибудь помочь мне добиться прогресса в поиске ответа на этот вопрос? Любая помощь будет высоко ценится.
Каждая ли NP-полная задача. допускают ограничение за полиномиальное время?
comment
Для подтверждения - ограничением будет бесконечное подмножество языка NP, принадлежащее P?
- person templatetypedef schedule 02.12.2014
comment
Учитывая две проблемы R и P, проблема R является ограничением P, если набор экземпляров R является подмножеством набора экземпляров P. Например, 3-SAT является ограничением SAT.
- person Cleverson schedule 02.12.2014
comment
Учитывается ли тривиальное ограничение пустого множества? Это определенно в P, но это не интересно.
- person templatetypedef schedule 02.12.2014
comment
Вы имеете в виду, например, для задачи TSP наличие графа без вершин? Что, если мы сделаем шаг назад и получим набор только с одним значением?
- person Cleverson schedule 02.12.2014
comment
Еще более абстрактно рассмотрим любую проблему, множество экземпляров которой пусто (возьмем любую невозможную проблему или тривиальную проблему, ответ на которую всегда отрицательный). Пустое множество — это подмножество всех проблем, поэтому пустая проблема тривиально является ограничением любой проблемы. Однако это не интересное ограничение, поскольку оно ничего не говорит вам о том, как извлечь интересную подзадачу из произвольной задачи NP.
- person templatetypedef schedule 02.12.2014
comment
Я думаю, что это имеет значение, потому что, на мой взгляд, это упражнение предназначено для того, чтобы показать, поняли ли мы концепцию ограничений. И это очень общий ответ.
- person Cleverson schedule 02.12.2014
Ответы (1)
Преобразование моего комментария в ответ - рассмотрим «пустую проблему», проблему, набор экземпляров которой пуст. Поскольку пустое множество является подмножеством каждого множества, эта проблема технически считается ограничением любого языка (включая языки, не входящие в NP). Это также проблема в P; вы можете построить TM с полиномиальным временем, который всегда отклоняет ввод. Таким образом, каждая задача в NP имеет ограничение полиномиального времени.
Однако мне все еще любопытно, есть ли у каждой задачи NP, набор экземпляров которой бесконечен, ограничение полиномиального времени, набор экземпляров которого также бесконечен. Это более интересный вопрос, ИМХО, и у меня сейчас нет ответа.
Надеюсь это поможет!
person
templatetypedef
schedule
01.12.2014
