RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika. Supplement // Archive
Prikl. Diskr. Mat. Suppl., 2013 Issue 6, Pages 112–116 (Mi pdma76)
Computational methods in discrete mathematics

Asymptotic solution of the recurrence relations in the analysis of splitting algorithms for SAT

V. V. Bykova

Institute of Mathematics and Computer Science, Siberian Federal University, Krasnoyarsk

Abstract: 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.

UDC: 519.712


© Steklov Math. Inst. of RAS, 2024