Impagliazzo, Paturi и Calabro, Impagliazzo, Paturi представили гипотезу экспоненциального времени (ETH) и гипотезу сильно экспоненциального времени (SETH). Грубо говоря, SETH говорит, что нет алгоритма, который решает SAT за время .
Мне было интересно, что бы это значило, чтобы сломать SETH. Нам определенно нужно найти алгоритм, который решает SAT менее чем за шагов, но я не совсем понимаю, какую вычислительную модель нам следует использовать. Насколько мне известно, результаты, основанные на SETH (см., Например, Сиган, Делл, Локштанов, Маркс, Недерлоф, Окамото, Патури, Саурабх, Вальстрем ), не должны делать предположений относительно базовой модели вычислений.
Предположим, например, что мы нашли алгоритм, который решает SAT за время используя пространство . Означает ли это автоматически, что мы можем найти машину Тьюринга, которая решает эту проблему за время ? Это ломает SETH?
источник