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

Описание

Перевод названия: 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

Место издания: Томск

Издатель: Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Национальный исследовательский Томский государственный университет

Авторы

Вхождение в базы данных