OpenAI представляет доказательство, опровергающее Exponential Time Hypothesis в Lean

In English
1 мин
OpenAI представляет доказательство, опровергающее Exponential Time Hypothesis в Lean

В OpenAI заявили, что доказали ложность Exponential Time Hypothesis (ETH) и даже проверили доказательство в Lean, из-за чего в математическом и компьютерно-научном сообществе — настоящий шок.

ETH — это гипотеза, которую обычно используют для установления нижних границ времени работы алгоритмов при решении NP-complete задач. Вкратце: если задача относится к классу «трудных», то как ни оптимизируй алгоритм, быстрее чем за 2^O(n), то есть быстрее экспоненциального времени, её решить нельзя — так утверждает гипотеза.

OpenAI утверждает, что для некоторого подмножества случаев ETH неверна. Если это правда, то множество результатов, выведенных на основе ETH, могут потерять силу, а оптимальные решения к задачам измениться. Я правильно всё вижу?..

https://x.com/danintheory/status/2114833682469122314?s=20

Оригинальная публикация

Авторы, указанные в источнике: c4lvinlocked

Материал опубликован Holder на основе внешнего источника.