NP-полная проблема с полиномиальным числом да-экземпляров?

15

У меня сложилось впечатление, что для каждой NP-полной задачи для бесконечно большого числа входных размеров число экземпляров yes на всех возможных входных данных размера (по крайней мере) экспоненциально по .NNN

Это правда? Можно ли это доказать (вероятно, только в предположении, что )? Или мы можем, может быть, искусственно, найти проблему, когда для всех (достаточно больших) число экземпляров yes не более чем полиномиальное от ?пNпNN

В основном, я рассуждаю так: при наличии экземпляра yes для 3-SAT мы можем идентифицировать литерал в каждом предложении, который делает его истинным, и заменить другую переменную в предложении еще одной переменной, не изменяя, что она выполнима. Так как мы можем сделать это с каждым предложением, это приводит к экспоненциальному количеству экземпляров yes. То же самое верно для многих других задач, таких как гамильтонова траектория: мы можем свободно менять ребра, которые не находятся на траектории Затем я смело рассуждаю о том, что поскольку сводимость заключается в том, что каким-то образом должны быть сохранены решения, она должна выполняться для всех NP-полных задач.

Кажется, это также справедливо для, возможно, NP-промежуточной проблемы изоморфизма графов (где мы можем свободно применять одинаковые изменения к обоим графам, если мы знаем отображение). Интересно, верно ли это и для целочисленной факторизации?

Альберт Хендрикс
источник

Ответы:

19

Это отдельный вопрос, является ли число случаев да экспоненциальным. (Можно предположить, что число случаев «да» может быть более чем полиномиальным, но менее экспоненциальным.) Гипотеза Бермана-Хартманиса здесь уместна; это означает, что все NP-полные задачи имеют экспоненциально много случаев да. Гипотеза остается открытой проблемой.

DW
источник