Информатика и ИИ · эксперимент
Преодолей предел
Сеть, группа людей, которые все знают друг друга, обходной путь 1985 года через перемножение матриц и гипотеза, продержавшаяся десятилетиями. Четыре вопроса, от начального уровня до продвинутого, о конце гипотезы о k-клике.
1 · Сформулируй, что доказано
Начальный
Что статья показывает о гипотезе о k-клике?
2 · Вычисли затраты 1985 года
Метод Нешетржила–Поляка находит k-клику примерно за n^(ωk/3) шагов. Возьми k = 9 и ω = 2, наименьшее значение, которое может иметь ω.
Средний
Какой показатель степени n даёт метод 1985 года?
3 · Объясни «даже при ω = 2»
Гипотеза предсказывает затраты n^(ωk/3). Точное значение ω неизвестно: оно не меньше 2, а статья приводит верхнюю оценку 9/4.
Продвинутый
Почему важно, что новый выигрыш сохраняется при любом ω, даже при ω = 2?
4 · Перенеси выигрыш
Задача Max-2-CSP, включающая Max-Cut и Max-2-SAT, с n булевыми переменными решалась примерно за 2^(ωn/3) шагов. Разбей переменные на девять групп, и каждое присваивание значений группе становится вершиной задачи о взвешенной клике из девяти вершин.
Продвинутый
Что новый алгоритм для клик даёт для этих задач?
Предел преодолён
—