Backtracking based k-SAT algorithms

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F15%3A00447653" target="_blank" >RIV/67985840:_____/15:00447653 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-642-27848-8_45-2" target="_blank" >http://dx.doi.org/10.1007/978-3-642-27848-8_45-2</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-27848-8_45-2" target="_blank" >10.1007/978-3-642-27848-8_45-2</a>

Result language
angličtina
Original language name
Backtracking based k-SAT algorithms
Original language description
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 declarenone 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.
Czech name
—
Czech description
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2015
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)