Number of the records: 1
Encyclopedia of Algorithms
- 1.0447653 - MÚ 2016 RIV DE eng M - Monography Chapter
Paturi, R. - Pudlák, Pavel - Saks, M. - Zane, F.
Backtracking based k-SAT algorithms.
Encyclopedia of Algorithms. Berlin: Springer, 2015 - (Kao, M.), s. 1-6. ISBN 978-3-642-27848-8
Institutional support: RVO:67985840
Keywords : theory of computation * algorithms
Subject RIV: BA - General Mathematics
http://link.springer.com/referenceworkentry/10.1007/978-3-642-27848-8_45-2
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.
Permanent Link: http://hdl.handle.net/11104/0249436
File Download Size Commentary Version Access Pudlak.pdf 1 132.6 KB Publisher’s postprint require
Number of the records: 1