Дагштуль
Как некоторые из вас, возможно, знают, мы с edwardahirsch-ем недавно ездили в Дагштуль на семинар под названием Moderately Exponential Time Algorithms. В Дагштуле по-прежнему очень и очень здорово. Они действительно делают всё, чтобы учёным там было максимально комфортно. Я даже не смог ничего придумать, когда увидел в анекте вопрос "Как сделать Дагштуль лучше?". Написал, в итоге, что можно было бы сделать более удобную форму поиска книг в их библиотеке (а то библиотека огромная, но искать можно только по ключевому слову, названию и автору, и как посмотреть все книги по алгоритмам, не очень ясно -- при запросе "algorithms" выдаётся туча просидингов, естественно). Ну, ещё они просят в какую-то большую книгу записать от руки абстракт доклада, но ведь традиция это.
Что касается научной составляющей, то интересных докладов было не так и много. Я, впрочем, экспоненциальными алгоритмами последний год не занимался. Рассказывать об интересных докладах здесь не буду, ибо не уверен, что меня читают хотя бы два человека, которые этой темой интересуются (но если вдруг кто-то найдётся всё же -- обращайтесь). Вместо этого я вам несколько фотографий покажу. Вы ведь все любите разглядывать фотографии, да? Особенно с жизнерадостным edwardahirsch-ем. По нему и так будет понятно, что в Дагштуле круто. А времени на отчёт у меня сейчас нет.
А ещё в конце поста приведу несколько открытых задач. На семинаре поднималось гораздо больше, на самом деле, но почти все задачи, которые я опущу, сводятся к улучшению какого-нибудь там знака после запятой, от чего я уже устал.
А вот и несколько обещанных открытых вопросов.
- Да, мы до сих пор не знаем, можно ли решить выполнимость за c^n, где c<2.
Но это, конечно, очень сложная задача. Многие даже верят в отрицательный ответ на этот вопрос. - Не так давно был представлен алгоритм, решающий раскраску графа за 2^n. Отметим, что совсем тривиальный алгоритм будет работать n^n. Когда-то давно было придуман алгоритм со временем работы 3^n. Полтом эта оценка опускалась до двух с чем-то, и вот только недавно была получена двойка. Алгоритм, говорят, довольно элегантный. Вопрос же здесь понятен: а можно ли быстрее?
- Похожая ситуация и с задачей MAX-2-SAT. Несколько лет назад Вильямс представил красивый алгоритм, решающий эту задачу за c^n. Это, в общем-то, единственный известный алгоритм с таким временем работы. А вопросов здесь целых два.Можно ли избавить этот алгоритм от экспоненциальной памяти? Можно ли MAX-3-SAT решить быстрее, чем 2^n?
- Есть, на самом деле, ещё пачка задач, для которых мы не знаем, решаются ли они за время c^n, в то время как оценка 2^n очевидна. Один из примеров -- задача о коммивояжёре.
- Было ещё несколько задач о приближённых алгоритмах. Мы знаем, что некоторых NP-трудные задачи нельзя константно приблизить за полиномиальное время, если P не равно NP. А за субэкспоненциальное можно?
- Следующий вопрос касается оценок относительно множества вершин графа: можно ли решить задачи Edge Coloring и/или Edge Clique Cover за время c^n хоть для какой-нибудь константы c?
- Как сказано выше, для многих задач мы не знаем алгоритмов, улучшающих тривиальные. Можем ли мы построить сведения, говорящие, что такой алгоритм есть у одной задачи тогда и только тогда, когда он есть у другой? Похожие результаты есть у Вильямса (из них, в частности, следует, что улучшить некоторый полиномиальный алгоритм не легче, чем решить выполнимость за c^n).
- Какое максимальное количество s-t сепараторов может быть в графе из n вершин? Несложно построить пример, в котором их 3^{n/3}, но можно ли больше? Насколько я понимаю, есть алгоритмы, которые для чего-то перебирают все такие сепараторы, причём делают это за линейное время от самого их количества.
- Ну, и последний вопрос, не особо связанный с алгоритмами. Обозначим через f(2n) количество различных рёберных раскрасок графа K_{2n} в (2n-1) цвет. Believe it or not, но человечеству известны значения функции f только для 2n<16. Итак, чему же равно f(16)? Как я понял, эта задач тесно связана с подсчётом различных латинских квадратов.