Počet záznamů: 1
Encyclopedia of Algorithms
- 1.0447653 - MÚ 2016 RIV DE eng M - Část monografie knihy
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
Institucionální podpora: RVO:67985840
Klíčová slova: theory of computation * algorithms
Kód oboru RIV: BA - Obecná matematika
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.
Trvalý link: http://hdl.handle.net/11104/0249436
Název souboru Staženo Velikost Komentář Verze Přístup Pudlak.pdf 1 132.6 KB Vydavatelský postprint vyžádat
Počet záznamů: 1