Backtracking based k-SAT algorithms

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Backtracking based k-SAT algorithms

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Backtracking based k-SAT algorithms

Popis výsledku anglicky

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.

Druh

C - Kapitola v odborné knize

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2015

Kód důvěrnosti údajů

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

Název knihy nebo sborníku

Encyclopedia of Algorithms

ISBN

978-3-642-27848-8

Počet stran výsledku

6

Strana od-do

1-6

Počet stran knihy

2591

Název nakladatele

Springer

Místo vydání

Berlin

Kód UT WoS kapitoly

—