A $2^{o(n)}$ Time Algorithm for 3-SAT · Hexagon
Anthropic опублікувала роботу, в якій заявляє про детермінований алгоритм для 3-SAT з часом роботи 2^{o(n)}, що спростовує Exponential Time Hypothesis (ETH). Стверджується, що алгоритм розв'язує навіть складнішу задачу підрахунку #3-SAT. За описом авторів, алгоритм знайшла внутрішня дослідницька модель Claude без людського втручання, результат формалізовано в Lean 4, а паралельно схожий результат нібито отримала модель OpenAI.