Geodesic
On the asymptotic solution of a~special type recurrence relations and the Kullmann--Luckhardt's technology
Prikladnaâ diskretnaâ matematika, no. 4 (2013), pp. 56-66.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: computational complexity of recursive algorithms, splitting algorithms, solving recurrence relations. 
@article{PDM_2013_4_a5,
     author = {V. V. Bykova},
     title = {On the asymptotic solution of a~special type recurrence relations and the {Kullmann--Luckhardt's} technology},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {56--66},
     publisher = {mathdoc},
     number = {4},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2013_4_a5/}
}
TY  - JOUR
AU  - V. V. Bykova
TI  - On the asymptotic solution of a~special type recurrence relations and the Kullmann--Luckhardt's technology
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2013
SP  - 56
EP  - 66
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2013_4_a5/
LA  - ru
ID  - PDM_2013_4_a5
ER  - 
%0 Journal Article
%A V. V. Bykova
%T On the asymptotic solution of a~special type recurrence relations and the Kullmann--Luckhardt's technology
%J Prikladnaâ diskretnaâ matematika
%D 2013
%P 56-66
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2013_4_a5/
%G ru
%F PDM_2013_4_a5
V. V. Bykova. On the asymptotic solution of a~special type recurrence relations and the Kullmann--Luckhardt's technology. Prikladnaâ diskretnaâ matematika, no. 4 (2013), pp. 56-66. http://geodesic.mathdoc.fr/item/PDM_2013_4_a5/

[1] Kormen T., Leizerson Ch., Rivest R., Algoritmy: postroenie i analiz, Vilyams, M., 2012

[2] Otpuschennikov I. V., Semënov A. A., “Tekhnologiya translyatsii kombinatornykh problem v bulevy uravneniya”, Prikladnaya diskretnaya matematika, 2011, no. 1(11), 96–115

[3] Vsemirnov M. A., Girsh E. A., Dantsin E. Ya., Ivanov S. V., “Algoritmy dlya propozitsionalnoi vypolnimosti i verkhnie otsenki ikh slozhnosti”, Teoriya slozhnosti vychislenii, VI, Zap. nauchn. sem. POMI, 277, SPb., 2001, 14–46 | MR | Zbl

[4] Davis M., Logemann G., and Loveland D., “A machine program for theorem-proving”, Comm. ACM, 5:7 (1962), 394–397 | DOI | MR | Zbl

[5] Davis M. and Putman H., “A computing procedure for quantification theory”, J. ACM, 7:3 (1960), 201–215 | DOI | MR | Zbl

[6] Franco J. and Gelder A. V., “A perspective on certain polynomial-time solvable classes of Satisfiability”, Discr. Appl. Math., 125:2–3 (2003), 177–214 | DOI | MR | Zbl

[7] Alekseev V. B., Nosov V. A., “NP-polnye zadachi i ikh polinomialnye varianty. Obzor”, Obozrenie prikladnoi i promyshlennoi matematiki, 4:2 (1997), 165–193

[8] Hirsch E. A., “New worst-case upper bounds for SAT”, J. Automated Reasoning, 24:4 (2000), 397–420 | DOI | MR | Zbl

[9] Kulikov A. S., Kutskov K., “Novye verkhnie otsenki dlya zadachi maksimalnoi vypolnimosti”, Diskretnaya matematika, 21:1 (2009), 139–157 | DOI | MR | Zbl

[10] Bykova V. V., “Matematicheskie metody analiza rekursivnykh algoritmov”, Zhurnal Sibirskogo federalnogo universiteta. Ser. Matematika i fizika, 1:3 (2008), 236–246

[11] Goloveshkin V. A., Ulyanov M. V., Teoriya rekursii dlya programmistov, Fizmatlit, M., 2006

[12] Gelfond A. O., Ischislenie konechnykh raznostei, Fizmatlit, M., 1959 | MR

[13] Grekhem R., Knut D., Patashnik O., Konkretnaya matematika. Osnovanie informatiki, Binom. Lab. znanii, M., 2006

[14] Bykova V. V., “Elastichnost algoritmov”, Prikladnaya diskretnaya matematika, 2010, no. 2(8), 87–95

[15] Poincare H., “Sur les equations lineaires aux differentielles ordinaires et aux differences finies”, Amer. J. Math., 7 (1885), 203–258 | DOI | MR

[16] Perron O., “Uber einen Satz des Herrn Poincare”, J. Reine Angewand. Math., 136 (1909), 17–34

[17] Bakhvalov N. S., Chislennye metody, Binom. Lab. znanii, M., 2006

[18] Kullmann O., “New methods for 3-SAT decision and worst-case analysis”, Theor. Computer Sci., 223 (1999), 1–72 | DOI | MR | Zbl

[19] Kullmann O., Luckhardt H., Deciding propositional tautologies: Algorithms and their complexity, Preprint, , 1997 http://www.cs.swan.ac.uk/~csoliver

[20] Kulikov A. S., Fedin S. S., “Avtomaticheskie dokazatelstva verkhnikh otsenok na vremya raboty algoritmov rasschepleniya”, Teoriya slozhnosti vychislenii, IX, Zap. nauchn. sem. POMI, 316, SPb., 2004, 111–128 | MR | Zbl