Počet záznamů: 1
Encyclopedia of Algorithms
- 1.
SYSNO ASEP 0447653 Druh ASEP M - Kapitola v monografii Zařazení RIV C - Kapitola v knize Název Backtracking based k-SAT algorithms Tvůrce(i) Paturi, R. (US)
Pudlák, Pavel (MU-W) RID, SAI
Saks, M. (US)
Zane, F. (US)Zdroj.dok. Encyclopedia of Algorithms. - Berlin : Springer, 2015 / Kao M.-Y. - ISBN 978-3-642-27848-8 Rozsah stran s. 1-6 Poč.str. 6 s. Poč.výt. 500 Poč.str.knihy 2591 Forma vydání Online - E Jazyk dok. eng - angličtina Země vyd. DE - Německo Klíč. slova theory of computation ; algorithms Vědní obor RIV BA - Obecná matematika Institucionální podpora MU-W - RVO:67985840 DOI 10.1007/978-3-642-27848-8_45-2 Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2016
Počet záznamů: 1