Выполняет ли каждый NP-полный запрос. допустим ограничение полиномиального времени?

Я должен ответить на этот вопрос как домашнее задание, но я нахожу очень мало материала для работы. Я понимаю, что такое NP-полная проблема и что такое ограничение. На мой взгляд, это утверждение верно, потому что вы всегда можете ограничить проблему, чтобы «облегчить задачу». Но я смотрю на него с высоты птичьего полета ... Может ли кто-нибудь помочь мне добиться определенного прогресса в поиске ответа на этот вопрос? Любая помощь будет высоко оценена.Выполняет ли каждый NP-полный запрос. допустим ограничение полиномиального времени?

источник

2014-12-01 Cleverson

Чтобы подтвердить - «ограничение» было бы бесконечным подмножеством языка NP, принадлежащего P? – templatetypedef

Учитывая две проблемы R и P, проблема R является ограничением P, если набор экземпляров R является подмножеством экземпляра множества P. Например, 3-SAT является ограничением SAT. – Cleverson

Задает ли тривиальное ограничение пустого множества? Это определенно в P, но это не «интересно». – templatetypedef

Преобразование моего комментария в ответ - рассмотрим «пустую проблему», проблему, набор экземпляров которой пуст. Так как пустое множество является подмножеством каждого множества, эта проблема технически считается ограничением любого языка (включая языки не в NP). Это также проблема в P; вы можете построить многочленную TM, которая всегда отклоняет ее вход. Поэтому каждая проблема в NP имеет ограничение на полиномиальное время.

Тем не менее, мне все же интересно узнать, есть ли каждая проблема, набор экземпляров которой бесконечен, имеет ограничение на полиномиальное время, набор экземпляров которого также бесконечен. Это более интересный вопрос, ИМХО, и у меня в настоящее время нет ответа.

Надеюсь, это поможет!

источник

2014-12-01 21:55:22 templatetypedef

Выполняет ли каждый NP-полный запрос. допустим ограничение полиномиального времени?

ответ

Смежные вопросы