Number of the records: 1
Encyclopedia of Algorithms
- 1.
SYSNO ASEP 0447653 Document Type M - Monograph Chapter R&D Document Type Monograph Chapter Title Backtracking based k-SAT algorithms Author(s) Paturi, R. (US)
Pudlák, Pavel (MU-W) RID, SAI
Saks, M. (US)
Zane, F. (US)Source Title Encyclopedia of Algorithms. - Berlin : Springer, 2015 / Kao M.-Y. - ISBN 978-3-642-27848-8 Pages s. 1-6 Number of pages 6 s. Number of copy 500 Number of pages 2591 Publication form Online - E Language eng - English Country DE - Germany Keywords theory of computation ; algorithms Subject RIV BA - General Mathematics Institutional support MU-W - RVO:67985840 DOI 10.1007/978-3-642-27848-8_45-2 Annotation Determination of the complexity of k-CNF satisfiability is a celebrated open problem: given a Boolean formula in conjunctive normal form with at most k literals per clause, find an assignment to the variables that satisfies each of the clauses or declare none exists. It is well known that the decision problem of k-CNF satisfiability is NP-complete for l>= 3. This entry is concerned with algorithms that significantly improve the worst-case running time of the naive exhaustive search algorithm, which is poly(n)2 n for a formula on n variables. Monien and Speckenmeyer [8] gave the first real improvement by giving a simple algorithm whose running time is ..., with ... for all k. In a sequence of results [1, 3, 5–7, 9–12], algorithms with increasingly better running times (larger values of ...) have been proposed and analyzed. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2016
Number of the records: 1