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