Počet záznamů: 1  

Encyclopedia of Algorithms

  1. 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 souboruStaženoVelikostKomentářVerzePřístup
    Pudlak.pdf1132.6 KBVydavatelský postprintvyžádat
     
Počet záznamů: 1  

  Tyto stránky využívají soubory cookies, které usnadňují jejich prohlížení. Další informace o tom jak používáme cookies.