Об асимптотике решений рекуррентных соотношений специального вида и технике Кульмана–Люкхардта

Обсуждаются проблемы решения рекуррентных соотношений, возникающих в анализе вычислительной сложности рекурсивных алгоритмов. Класс рассматриваемых алгоритмов ограничен алгоритмами расщепления, а именно DPLL-алгоритмами, предназначенными для решения задачи пропозициональной выполнимости. Исследована техника Кульмана–Люкхардта, традиционно применяемая при исследовании вычислительной сложности алгоритмов расщепления. Предложена теорема, устанавливающая верхние оценки времени выполнения DPLL-алгоритма в случае сбалансированного расщепления. Теорема расширяет возможности техники Кульмана–Люкхардта, так как учитывает неоднородность рекуррентного соотношения, описывающего время работы DPLL-алгоритма.