Вычислительная модель в SETH

11

Impagliazzo, Paturi и Calabro, Impagliazzo, Paturi представили гипотезу экспоненциального времени (ETH) и гипотезу сильно экспоненциального времени (SETH). Грубо говоря, SETH говорит, что нет алгоритма, который решает SAT за время . 1.99n

Мне было интересно, что бы это значило, чтобы сломать SETH. Нам определенно нужно найти алгоритм, который решает SAT менее чем за шагов, но я не совсем понимаю, какую вычислительную модель нам следует использовать. Насколько мне известно, результаты, основанные на SETH (см., Например, Сиган, Делл, Локштанов, Маркс, Недерлоф, Окамото, Патури, Саурабх, Вальстрем ), не должны делать предположений относительно базовой модели вычислений.2n

Предположим, например, что мы нашли алгоритм, который решает SAT за время 1.5n используя пространство 1.5n . Означает ли это автоматически, что мы можем найти машину Тьюринга, которая решает эту проблему за время 1.99n ? Это ломает SETH?

Алекс Головнев
источник

Ответы:

18

SETH говорит, что для всех существует такое , что для -SAT требуется времени, чтобы найти решение в худшем случае. Вычислительная модель, как правило, принимается как модель машины с произвольным доступом или машины указателя, которая обеспечивает временной доступ к хранилищу из элементов, и, как правило, предполагается также вероятностной с ограниченной ошибкой.δ<1kk2δnO(logN)N

Насколько я знаю, открыто, могут ли алгоритмы времени на такой модели быть переведены на двухленточные машины Тьюринга, работающие за времени. Тем не менее, доказательство того, что такой перевод не возможно будет отделить Многоленточный Тьюринг машину от случайных машин доступа, которые будут иметь несколько очень интригующее последствия. С одной стороны , было бы доказать , что СБ не разрешима в квазилинейное время на многоленточных машинах Тьюринга (потому что, если СБ может быть решен с помощью таких многоленточных машин, то машины с произвольным доступом могут2δn2δnpoly(n)быть эффективно смоделированы на многоленточных станках Тьюринга) Обратите внимание, что многие вычислительные примитивы (такие как сортировка, оценка цепей, простое динамическое программирование) могут быть эффективно реализованы на машинах Тьюринга с несколькими лентами. Одной из соответствующих ссылок на эти проблемы является Риган, «О разнице между машинным временем Тьюринга и машинным временем с произвольным доступом».

Чтобы ответить на ваши конкретные вопросы: нет, многоканальная машина Тьюринга здесь не подразумевается автоматически, но да, такой «алгоритм» для SAT (при обычной модели произвольного доступа) сломает SETH.

Райан Уильямс
источник
3
Спасибо! Вы определенно ответили на мой вопрос, но разве СЕТ не говорит, что ? δ=1
Алексей Головнев
2
Не совсем. Я исправил квантификаторы.
Райан Уильямс
Как насчет квантовых компьютеров в этом контексте? Есть ли какие-либо последствия алгоритма Гровера в этом контексте? Есть ли работа по предположению квантового аналога ETH?
Мартин Шварц
Что касается квантовых алгоритмов, Гровер дает около времени для CNF SAT. Но можно представить «квантовую SETH», которая утверждает, что это ускорение квадратного корня является наилучшим возможным.
2n/2
Райан Уильямс
Конечно, но разве это ускорение лучше, чем классическое, и «кватум SETH» уже имеют какие-то последствия в каком-то другом месте в теории сложности? Просто интересуюсь.
Мартин Шварц,