Geodesic
Asymptotic solution of the recurrence relations in the analysis of splitting algorithms for SAT
Prikladnaya Diskretnaya Matematika. Supplement, no. 6 (2013), pp. 112-116.

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

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.
Keywords: splitting algorithms, computational complexity. 
@article{PDMA_2013_6_a50,
     author = {V. V. Bykova},
     title = {Asymptotic solution of the recurrence relations in the analysis of splitting algorithms for {SAT}},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {112--116},
     publisher = {mathdoc},
     number = {6},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2013_6_a50/}
}
TY  - JOUR
AU  - V. V. Bykova
TI  - Asymptotic solution of the recurrence relations in the analysis of splitting algorithms for SAT
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2013
SP  - 112
EP  - 116
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2013_6_a50/
LA  - ru
ID  - PDMA_2013_6_a50
ER  - 
%0 Journal Article
%A V. V. Bykova
%T Asymptotic solution of the recurrence relations in the analysis of splitting algorithms for SAT
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2013
%P 112-116
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2013_6_a50/
%G ru
%F PDMA_2013_6_a50
V. V. Bykova. Asymptotic solution of the recurrence relations in the analysis of splitting algorithms for SAT. Prikladnaya Diskretnaya Matematika. Supplement, no. 6 (2013), pp. 112-116. http://geodesic.mathdoc.fr/item/PDMA_2013_6_a50/

[1] 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 | Zbl

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

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

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

[5] Kullmann O., Luckhardt H., Deciding propositional tautologies: Algorithms and their complexity, Preprint, , 1997 http://cs-svr1.swan.ac.uk/c̃soliver

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

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

[8] Kormen T., Leizerson Ch., Rivest R., Algoritmy: postroenie i analiz, MTsNMO, M., 1999

[9] 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 | Zbl

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