HomeIssuesAsymptotic solution of the recurrence relations in the analysis of splitting algorithms for sat

Asymptotic solution of the recurrence relations in the analysis of splitting algorithms for sat | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 6 (Приложение).

The traditional technique for analysis of splitting algorithms for SAT problem is considered. A theorem establishing the upper bounds for execution time of algorithms in the case of balanced splitting is offered.
Download file
Counter downloads: 289
  • Title Asymptotic solution of the recurrence relations in the analysis of splitting algorithms for sat
  • Headline Asymptotic solution of the recurrence relations in the analysis of splitting algorithms for sat
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 6 (Приложение)
  • Date:
  • DOI
Keywords
алгоритмы расщепления, сложность вычислений, splitting algorithms, computational complexity
Authors
References
Всемирное М. А., ГиршЭ.А., Данцин Е. Я., Иванов С. В. Алгоритмы для пропозициональной выполнимости и верхние оценки их сложности // Теория сложности вычислений. VI. Зап. научн. сем. ПОМИ. СПб., 2001. Т. 277. С. 14-46.
Davis M. and Putman H. A computing procedure for quantification theory // J. ACM. 1960. No. 7(3). P. 201-215.
Davis M., Logemann G., and Loveland D. A machine program for theorem-proving // Comm. ACM. 1962. No. 5(7). P. 394-397.
Kullmann O. New methods for 3-SAT decision and worst-case analysis // Theor. Comp. Sci. 1999. No. 223. P. 1-72.
Kullmann O. and Luckhardt H. Deciding propositional tautologies: Algorithms and their complexity / Preprint. 1997. http://cs-svr1.swan.ac.uk/~csoliver
Быкова В. В. Эластичность алгоритмов // Прикладная дискретная математика. 2010. №2(8). С. 87-95.
Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М.: Бином. Лаборатория знаний, 2006.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 1999.
Куликов А. С., Федин С. С. Автоматические доказательства верхних оценок на время работы алгоритмов расщепления // Теория сложности вычислений. IX. Зап. научн. сем. ПОМИ. СПб., 2004. Т. 316. С. 111-128.
Быкова В. В. Математические методы анализа рекурсивных алгоритмов // Журнал Сибирского федерального университета. Сер. Математика и физика. 2008. №1(3). С. 236-246.
Asymptotic solution of the recurrence relations in the analysis of splitting algorithms for sat | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 6 (Приложение).
Asymptotic solution of the recurrence relations in the analysis of splitting algorithms for sat | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 6 (Приложение).
Download full-text version
Counter downloads: 1886
Download file