Гипотеза экспоненциального времени

Гипотеза экспоненциального времени (англ. Exponential Time Hypothesis, ETH) — это недоказанное предположение в теории сложности вычислений, которое утверждает, что задача о выполнимости булевых формул (SAT) не может быть решена существенно быстрее, чем за экспоненциальное время относительно числа переменных. Более формально, ETH постулирует, что не существует детерминированного алгоритма, решающего 3-СПК (3-SAT) за время \(2^{o(n)}\), где \(n\) — число переменных в формуле. Эта гипотеза является одним из центральных постулатов параметризованной сложности и тонких границ сложности (fine-grained complexity), позволяя устанавливать нижние границы времени работы алгоритмов для множества других задач.

История

Гипотеза была сформулирована в 1999 году американским учёным Расселом Импальяццо (Russell Impagliazzo) совместно с Рахулом Партасарати (Rahul Parthasarathy) и Ави Вигдерсоном (Avi Wigderson). Она возникла как уточнение более слабой гипотезы P ≠ NP, которая не даёт конкретных оценок времени решения NP-полных задач. ETH предлагает конкретную экспоненциальную нижнюю границу, что позволяет проводить более точный анализ сложности.

Первоначально Импальяццо и его соавторы изучали взаимосвязь между временем решения SAT и другими задачами. Они показали, что если ETH верна, то многие классические NP-полные задачи, такие как задача о вершинном покрытии (Vertex Cover) или задача о клике (Clique), также не могут быть решены субэкспоненциально. Впоследствии гипотеза стала фундаментом для целого направления — тонких границ сложности (fine-grained complexity theory), где исследуются точные экспоненты времени работы алгоритмов.

Формулировка и варианты

Классическая ETH

Основная формулировка: Не существует алгоритма, решающего 3-SAT за время \(2^{o(n)}\). Здесь \(n\) — число переменных, а \(o(n)\) означает «малое-о» от \(n\) (то есть функция, растущая строго медленнее линейной). Это означает, что любой алгоритм для 3-SAT требует времени не менее \(c^n\) для некоторой константы \(c > 1\).

Сильная гипотеза экспоненциального времени (SETH)

Более сильное предположение — Сильная гипотеза экспоненциального времени (Strong Exponential Time Hypothesis, SETH) — утверждает, что для любого \(\varepsilon > 0\) существует такое целое \(k \ge 3\), что \(k\)-SAT не может быть решена за время \(O(2^{(1-\varepsilon)n})\). Иными словами, по мере увеличения \(k\) константа в основании экспоненты стремится к 1, но никогда не достигает её. SETH имеет ещё более широкие последствия для тонких границ сложности.

Последствия для других задач

Если ETH верна, то для многих задач можно доказать точные нижние границы времени работы. Ниже приведены некоторые важные следствия.

Задача о вершинном покрытии

Для графа с \(n\) вершинами задача о вершинном покрытии (Vertex Cover) может быть решена за время \(O(1.6181^n)\) с помощью алгоритма поиска с возвратом. ETH утверждает, что не существует алгоритма со временем \(2^{o(n)}\), то есть константа 1.6181 не может быть улучшена до 1 (субэкспоненциальный случай).

Задача о клике

Задача о клике (Clique) в графе с \(n\) вершинами, согласно ETH, не может быть решена за время \(2^{o(n)}\). Более того, для задачи о клике размера \(k\) (параметризованная версия) ETH даёт нижнюю границу \(f(k) \cdot n^{o(k)}\), что означает отсутствие алгоритма с полиномиальным временем при фиксированном \(k\).

Задача о сумме подмножеств

Для задачи о сумме подмножеств (Subset Sum) с \(n\) числами ETH предсказывает, что не существует алгоритма со временем \(2^{o(n)}\). Это согласуется с известным результатом: лучший алгоритм работает за \(O(2^{n/2})\) (встреча посередине), и улучшение до \(2^{o(n)}\) опровергло бы ETH.

Задачи на графах

ETH также используется для доказательства нижних границ для задач, таких как:

• Задача о гамильтоновом пути (Hamiltonian Path) — не решается за \(2^{o(n)}\).
• Задача о доминирующем множестве (Dominating Set) — не решается за \(2^{o(n)}\).
• Задача о раскраске графа (Graph Coloring) — не решается за \(2^{o(n)}\) для 3-раскраски.

Связь с параметризованной сложностью

В параметризованной сложности ETH играет ключевую роль при доказательстве того, что задача не принадлежит классу FPT (фиксированно-параметрически разрешимых задач). Если задача является W[1]-трудной (например, задача о клике с параметром \(k\)), то при выполнении ETH она не может быть решена за время \(f(k) \cdot n^{O(1)}\), где \(f(k)\) — произвольная вычислимая функция. Это означает, что экспонента в \(n\) обязательно зависит от \(k\).

Критика и статус

ETH не является доказанной теоремой; её истинность зависит от фундаментального вопроса P ≠ NP. Большинство специалистов в области теории сложности склоняются к тому, что ETH верна, поскольку она согласуется с интуитивными представлениями о сложности SAT и не противоречит известным результатам. Однако существуют и скептические взгляды: некоторые исследователи допускают возможность существования субэкспоненциальных алгоритмов для 3-SAT, что опровергло бы ETH.

В 2020-е годы были получены некоторые результаты, ослабляющие ETH. Например, в 2022 году группа учёных предложила алгоритм для 3-SAT, работающий за время \(O(1.307^n)\), что лишь незначительно лучше тривиального \(2^n\), но не опровергает ETH, так как константа всё ещё больше 1. Полное опровержение потребовало бы алгоритма со временем \(2^{o(n)}\), чего пока не достигнуто.

Применение в алгоритмической теории

ETH широко используется для:

• Доказательства нижних границ — установления того, что для данной задачи не существует алгоритма быстрее определённого порога.
• Классификации задач — разделения задач на те, которые могут быть решены субэкспоненциально, и те, которые требуют полной экспоненты.
• Анализа приближённых алгоритмов — ETH позволяет доказывать, что некоторые задачи не имеют полиномиальных приближённых схем (PTAS) с определённой точностью.

Интересные факты

• ETH тесно связана с гипотезой о временной иерархии (Time Hierarchy Theorem), но в отличие от неё не является доказанной.
• В 2018 году была предложена гипотеза экспоненциального времени для квантовых вычислений (QETH), которая утверждает, что квантовые компьютеры также не могут решить SAT за субэкспоненциальное время.
• ETH используется в криптографии для обоснования стойкости некоторых криптосистем: если ETH верна, то взлом определённых схем требует экспоненциального времени.

Источники

• Impagliazzo, R., Parthasarathy, R., & Wigderson, A. (1999). Exponential Time Hypothesis. Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC).
• Cygan, M., Fomin, F. V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., & Saurabh, S. (2015). Parameterized Algorithms. Springer.
• Williams, R. (2013). Exponential Time Hypothesis. In: Encyclopedia of Algorithms. Springer.
• Aaronson, S. (2005). Quantum Computing and the Exponential Time Hypothesis. arXiv:quant-ph/0507242.