В репозитории OpenAI на GitHub был опубликован препринт научной статьи, посвященной пересмотру основ теории вычислительной сложности. Работа под названием «The Exponential Time Hypothesis Is False» ставит под сомнение состоятельность гипотезы экспоненциального времени (Exponential Time Hypothesis, ETH), которая десятилетиями считалась краеугольным камнем в анализе алгоритмов.
Суть вопроса
Гипотеза экспоненциального времени утверждает, что некоторые задачи, такие как классическая задача выполнимости булевых формул (3-SAT), не могут быть решены за субэкспоненциальное время. Проще говоря, ETH постулирует существование фундаментального барьера сложности для определенных классов задач, который невозможно преодолеть с помощью более эффективных алгоритмов.
Если утверждения авторов нового исследования окажутся верными и пройдут процесс рецензирования, это повлечет за собой значительные изменения в теоретической информатике:
- Пересмотр нижних границ сложности для огромного количества алгоритмических задач.
- Изменение подходов к оценке эффективности программных решений.
- Потенциальный прорыв в решении задач, которые ранее считались практически невыполнимыми за разумное время.
На данный момент документ доступен в открытом доступе для экспертного сообщества. Математическое обоснование, представленное в препринте, требует тщательной проверки, так как опровержение столь устоявшейся гипотезы может перевернуть современные представления о границах вычислимости. Учитывая сложность темы, научному миру предстоит масштабная дискуссия, прежде чем выводы авторов будут приняты как доказанный факт.
Источник: github.com