Впечатлился когда-то вот этим докладом Бьорнера, решил про него написать.
Есть любопытная деятельность на стыке комбинаторной топологии и теории сложности алгоритмов. На мой взгляд, к ней можно естественно подойти как-то так.
Начнем с баяна: сортировки массива. Пусть дан массив длины n из вещественных чисел. Будем считать пока для простоты, что все элементы массива попарно различны. Надо массив отсортировать. Википедия нам говорит, что наиболее эффективные алгоритмы сортируют массив за время O(n*log n). Почему нельзя быстрее?
Объяснение: сортировка нам в качестве ответа выдает перестановку множества из n элементов. Всего количество возможных перестановок, т.е. потенциальных вариантов ответа на задачу, равно n!. Если мы для решения задали x вопросов типа "Да-Нет" (например, вопросов на сравнение элементов массива), то количество итоговых комбинаций ответов, которые мы сможем получить, равно 2^x. Если мы хотим покрыть все потенциальные возможности ответов, то должно выполняться 2^x>n!, т.е. x>log(n!)=n*log n. Просто и со вкусом.
Теперь рассмотрим такую задачу: дан массив длины n, надо понять, есть ли в нем повторы, т.е. равные элементы. Задача, очевидно, решается за O(n*log n): отсортируем массив, а потом проверим все последовательные пары. Но почему конкретно эту задачу нельзя решить быстрее? Предыдущее рассуждение не применимо: у нас в качестве ответа на задачу получается либо Да (есть повторы), либо Нет (нет повторов). Надо уточнить, что подразумевается под сложностью.
Если под сложностью понимать количество произвольных "Да-Нет"-вопросов, требуемых для ответа на поставленный вопрос, то сложность будет равна 1. Действительно, можно обойтись всего одним вопросом: верно ли, что произведение П разностей (a[i]-a[j]) по всем парам индексов i<j равно 0? Иными словами, с математической точки зрения мы можем просто спросить: правда ли, что n-мерный вектор (a[1],...,a[n]) лежит в конфигурации диагональных гиперплоскостей X(n), т.е. в объединении гиперплоскостей вида x_i=x_j? Это, конечно, совершенно бессмысленная трактовка задачи: на практике мы кучу времени потратим на вычисление "дискриминанта" П, там ведь порядка n^2 умножений.
Поэтому давайте ограничимся вопросами следующего вида. Разрешим (мгновенно) вычислять любую линейную функцию от элементов массива, и сравнивать результат ее вычисления с нулем. Таким образом, мы строим тернарное дерево решений, у которого в каждом узле происходит сравнение некоторой линейной функции с нулем: ответами могут быть <,=,>. Сложностью алгоритма будем называть высоту такого дерева, т.е. максимальное количество произведенных сравнений.
Обобщим задачу: пусть M - подмножество в R^n, и требуется решить задачу принадлежности массива (a[1],...,a[n]) подмножеству M с помощью описанного выше дерева решений с линейными вопросами. Очевидно, что задача в принципе разрешима только если множество M является объединением конечного числа полиэдров (было бы странно пытаться выяснить принадлежность точки параболе, задавая лишь линейные вопросы).
Так вот Добкин-Липтон'75 доказали, что сложность задачи принадлежности массива множеству M ограничена снизу числом log c(M), логарифмом числа компонент связности множества. Возвращаясь к задаче о повторах в массиве: нам нужно выяснить, принадлежит ли массив (a[1],...,a[n]) диагональной конфигурации X(n). Или, эквивалентно, принадлежит ли массив дополнению R^n\X(n)? Но дополнение до диагональной конфигурации - это объединение открытых камер Вейля типа А - их столько же, сколько и перестановок, то есть n!. Поэтому в задаче о повторах в массиве опять же получаем оценку снизу для сложности log(n!)=n*log(n).
Ну хорошо, теперь рассмотрим задачу о повторах в массиве комплексных чисел. Понятно, что сложность такая же, как и в вещественном случае: если бы мы умели быстро решать задачу с комплексными числами, то справились бы и с вещественной. Но формально Добкин-Липтон в комплексном случае не работают: как сама комплексная диагональная конфигурация, так и ее дополнение - связные множества.
Однако Бьорнер-Ловаш'92-94 доказали, что число компонент связности из оценки Добкина-Липтона можно заменить на модуль эйлеровой характеристики. А потом еще усилили: можно вообще взять сумму всех чисел Бетти.
Это можно применить к задаче наличия k-кратных повторов в массиве. В этой задаче нужно определить принадлежность массива дополнению до конфигурации X(n,k) плоскостей вида x_{i_1}=...=x_{i_k}, где i_1<...<i_k пробегает по всем возможным k-подмножествам индексов. При k>2 тут опять же Добкин-Липтон не работают: плоскости имеют коразмерность, бОльшую единицы, а значит их дополнение - связно. Естественно оценивать через числа Бетти.
Числа Бетти дополнения до произвольной конфигурации плоскостей можно вычислить по формуле Горески-Макферсона, это отдельная история. Бьорнер-Ловаш посчитали числа Бетти дополнения до X(n,k) всякими страшными комбинаторными ухищрениями (лексикографические шеллинги). И в итоге для задачи о k-кратных повторах в массиве опять же получили оценку O(n*log n), т.е. асимптотически ничего лучше, чем отсортировать массив и проверить все окошки из k подряд идущих чисел, - сделать нельзя. Гомологии дополнения до конфигурации мешают!
А теперь план, как доказать неравенство классов P и NP - из слайдов Бьорнера. Учитывая давность доклада, и того, что задача тысячелетия по прежнему открыта, надо полагать, дело не выгорело. Хотя, возможно, просто никто это до ума не довел.
Забудем про вещественные числа, будем работать с булями. Рассмотрим задачу о принадлежности булевой строчки некоторому подмножеству M булева куба {0,1}^n. Собственно, произвольные задачи в теории сложности как-то так и формализуются, как будто. Подмножество M можно рассматривать как алгебраическое многообразие над конечным полем F_2. У этого многообразия (или у его дополнения) можно определить этальные когомологии с коэффициентами в l-адических числах, для нечетных l. Можно определить этальные числа Бетти (на этальных когомологиях еще и автоморфизм Фробениуса действует, и там всякие дзета-функции возникают, но эти ужасы, авось, и не пригодятся). План Бьорнера:
(1) Доказать, что сложность выполнения алгоритма ограничена чем-то зависящим от суммы этальных чисел Бетти. Логарифмом, например, как в случае вещественных чисел и сингулярных гомологий.
(2) Взять какую-нибудь NP-полную задачу, формализовать в виде алгебраического многообразия M над F_2.
(3) Посчитать этальные когомологии M, убедиться, что числа Бетти дофига какие большие.
(4) Значит задача быстро не решается. Profit!
Комментариев нет:
Отправить комментарий