Верхние и нижние оценки на сложность вычислительных задач

За прошедшие с начала обучения в Computer Science центре полтора года я занимался доказательством верхних и нижних оценок на сложность алгоритмов под руководством Александра Куликова. Хоть эти две задачи и связаны, они также сильно различаются. Чтобы доказать верхнюю оценку, достаточно привести алгоритм и оценить его время работы. Для доказательства же нижней оценки нужно как-то умудриться показать, что ни один быстрый алгоритм не решает рассматриваемую вычислительную задачу. Для доказательства нижних оценок, как правило, рассматривается модель булевых схем. Такую модель, с одной стороны, проще анализировать. С другой стороны, любой алгоритм можно переделать в последовательность схем. Задача доказательства нижней оценки формулируется следующим образом: дана функция $f:{0,1}^n \rightarrow {0,1}$ , какое минимальное количество битовых бинарных операций, необходимых для вычисления $f$? Несложным подсчётом показывается, что для большинства функций нужно будет хотя бы $\Omega(\frac{2^n}{n})$ операций. В то же время лучшие нижние оценки линейны! Вместе с Олей Меланич (аспиранткой ПОМИ РАН) нам удалось привести очень простое доказательство нижней оценки $5n−o(n)$ для довольно широкого и одновременно простого класса функций. Это рекордная известная на данный момент нижняя оценка на схемную сложность над базисом $U_2$ (такая же оценка была доказана в 2002 году японскими учёными Kazuo Iwama и Hiroki Morizumi, но их доказательство гораздо сложнее). Статья по результатам исследований была опубликована в трудах конференции Computability in Eurpoe 2012, которая прошла летом 2012 в Кембридже и была приурочена к юбилею Алана Тьюринга. Из-за проблем с получением английской визы мне, к сожалению не удалось поучаствовать в этой конференции. Для тех, кто заинтересовался темой: слайды и черновик статьи.

Параллельно я пытался придумать новые точные и приближённые алгоритмы для задачи о надстроке. Формулировка этой задачи довольно проста: даны n строк, нужно найти самую короткую строку, содержащую все эти n строк в качестве подстрок. Задача NP-трудная, поэтому рассчитывать на полиномиальные алгоритмы для этой задачи не приходится. Вообще, что касается точных алгоритмов, то самый быстрый алгоритм для данной задачи имеет время работы порядка $2^n$. Доказать верхнюю оценку $1.99^n$ — открытый вопрос. Задача эта особенно интересна, так как относится к классу очень активно сейчас исследуемых перестановочных задач. Также активно изучаются приближённые алгоритмы. Задачей такого алгоритма является быстрое нахождение надстроки, которая, возможно, и не является кратчайшей, но зато гарантированно не сильно хуже кратчайшей. Лучшее текущее приближение (отношение длины приближенной строки к оптимальной) $2\frac{11}{23}$ было получено совсем недавно польским учёным по имени Marcin Mucha. Совместно с Сашей Головнёвым(выпускником Академического университета РАН, а сейчас — аспирантом New York University) нам удалось получить более сильные оценки для частного случая, когда входные строки не слишком длинные. В частности, для строк длины 3 мы разработали точный алгоритм со временем работы $3^\frac{n}{3}$ и приближённый алгоритм с ошибкой $1\frac{1}{3}$. Статья по результатам исследований принята на конференцию Symposium on Combinatorial Pattern Matching 2013, которая пройдёт этим летом в Германии и на которой будет праздноваться сорокалетие суффиксных деревьев. По мотивам исследований я сделал доклад на семинаре Computer Science клуба.