Когда мы хотим доказать , что является -полных, то стандартный подход выставляться полиномиальное время вычислимой сокращение многих один из известного -полных задачи в . В этом контексте нам не нужно жестко ограничивать время выполнения сокращения. Достаточно иметь любую полиномиальную границу, что позволяет ей иметь очень высокую степень.
Тем не менее, для естественных задач оценка, как правило, является полиномом низкой степени (давайте определим низкий как что-то однозначным). Я не утверждаю, что так должно быть всегда, но я не знаю контрпример.
Вопрос: есть ли контрпример? Это было бы вычисляемым множителем многозначным множителем между двумя естественными неполными задачами, так что в этом же случае не известно никакого быстрого сокращения, а наилучшим известным ограничением времени полинома является полином высокого порядка.
Примечание: Большие или даже огромные показатели иногда необходимы для естественных задач в , см. Алгоритмы полиномиального времени с огромным показателем / постоянной . Интересно, происходит ли то же самое в сокращениях среди естественных проблем?
источник
Ответы:
Аллендер предполагает, что ответ - нет:
Ссылка:
Э. Аллендер и М. Коцки. Усиление нижних оценок посредством самовосстановления . Журнал ACM 57, 3, статья 14 (март 2010).
источник