Перевод названия: On the asymptotic solution of a special type recurrence relations and the Kullmann — Luckhardt''s technology
Тип публикации: статья из журнала
Год издания: 2013
Ключевые слова: computational complexity of recursive algorithms, Splitting algorithms, solving recurrence relations, вычислительная сложность рекурсивных алгоритмов, алгоритмы расщепления, решение рекуррентных соотношений
Аннотация: Обсуждаются проблемы решения рекуррентных соотношений, возникающих в анализе вычислительной сложности рекурсивных алгоритмов. Класс рассматриваемых алгоритмов ограничен алгоритмами расщепления, а именно DPLL-ал-горитмами, предназначенными для решения задачи пропозициональной выполнимости. Исследована техника Кульмана — Люкхардта, тПоказать полностьюрадиционно применяемая при исследовании вычислительной сложности алгоритмов расщепления. Предложена теорема, устанавливающая верхние оценки времени выполнения DPLL-алго-ритма в случае сбалансированного расщепления. Теорема расширяет возможности техники Кульмана — Люкхардта, так как учитывает неоднородность рекуррентного соотношения, описывающего время работы DPLL-алгоритма. The problem of solving recurrence relations that arise in the analysis of the computational complexity of recursive algorithms is discussed. The research is only related to splitting algorithms, namely, DPLL-algorithms, which are named after the author's names by the first letters (Davis, Putman, Logemann, Loveland), and are designed to solve the problem SAT. The technology by Kullmann — Luckhardt, which is traditionally used in the analysis of the computational complexity of splitting algorithms, is explored. A theorem containing an upper estimate for the algorithm time is proved in the case of balanced splitting. The theorem extends the capabilities of the Kullmann — Luckhardt's technology.
Журнал: Прикладная дискретная математика
Выпуск журнала: № 4
Номера страниц: 56-66
ISSN журнала: 20710410
Место издания: Томск
Издатель: Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Национальный исследовательский Томский государственный университет