Standard
Deterministic algorithms for k-SAT based on covering codes and local search. / Dantsin, Evgeny; Goerdt, Andreas; Hirsch, Edward A.; Schöning, Uwe.
Automata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings. ed. / Ugo Montanari; Emo Welzl; Jose D. P. Rolim. Springer Nature, 2000. p. 236-247 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1853).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
Harvard
Dantsin, E, Goerdt, A
, Hirsch, EA & Schöning, U 2000,
Deterministic algorithms for k-SAT based on covering codes and local search. in U Montanari, E Welzl & JDP Rolim (eds),
Automata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1853, Springer Nature, pp. 236-247, 27th International Colloquium on Automata, Languages and Programming, ICALP 2000, Geneva, Switzerland,
9/07/00.
APA
Dantsin, E., Goerdt, A.
, Hirsch, E. A., & Schöning, U. (2000).
Deterministic algorithms for k-SAT based on covering codes and local search. In U. Montanari, E. Welzl, & J. D. P. Rolim (Eds.),
Automata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings (pp. 236-247). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1853). Springer Nature.
Vancouver
Dantsin E, Goerdt A
, Hirsch EA, Schöning U.
Deterministic algorithms for k-SAT based on covering codes and local search. In Montanari U, Welzl E, Rolim JDP, editors, Automata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings. Springer Nature. 2000. p. 236-247. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
Author
BibTeX
@inproceedings{f8163fe25f5d4be298b48d0de0cbf8af,
title = "Deterministic algorithms for k-SAT based on covering codes and local search",
abstract = "We show that satisfiability of formulas in k-CNF can be decided deterministically in time close to (2k/(k + 1))n, where n is the number of variables in the input formula. This is the best known worst-case upper bound for deterministic k-SAT algorithms. Our algorithm can be viewed as a derandomized version of Sch{\"o}ning{\textquoteright}s probabilistic algorithm presented in [15]. The key point of our algorithm is the use of covering codes together with local search. Compared to other “weakly exponential” algorithms, our algorithm is technically quite simple. We also show how to improve the bound above by moderate technical effort. For 3-SAT the improved bound is 1.481n.",
author = "Evgeny Dantsin and Andreas Goerdt and Hirsch, {Edward A.} and Uwe Sch{\"o}ning",
year = "2000",
month = jan,
day = "1",
language = "English",
isbn = "9783540450221",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "236--247",
editor = "Ugo Montanari and Emo Welzl and Rolim, {Jose D. P.}",
booktitle = "Automata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings",
address = "Germany",
note = "27th International Colloquium on Automata, Languages and Programming, ICALP 2000 ; Conference date: 09-07-2000 Through 15-07-2000",
}
RIS
TY - GEN
T1 - Deterministic algorithms for k-SAT based on covering codes and local search
AU - Dantsin, Evgeny
AU - Goerdt, Andreas
AU - Hirsch, Edward A.
AU - Schöning, Uwe
PY - 2000/1/1
Y1 - 2000/1/1
N2 - We show that satisfiability of formulas in k-CNF can be decided deterministically in time close to (2k/(k + 1))n, where n is the number of variables in the input formula. This is the best known worst-case upper bound for deterministic k-SAT algorithms. Our algorithm can be viewed as a derandomized version of Schöning’s probabilistic algorithm presented in [15]. The key point of our algorithm is the use of covering codes together with local search. Compared to other “weakly exponential” algorithms, our algorithm is technically quite simple. We also show how to improve the bound above by moderate technical effort. For 3-SAT the improved bound is 1.481n.
AB - We show that satisfiability of formulas in k-CNF can be decided deterministically in time close to (2k/(k + 1))n, where n is the number of variables in the input formula. This is the best known worst-case upper bound for deterministic k-SAT algorithms. Our algorithm can be viewed as a derandomized version of Schöning’s probabilistic algorithm presented in [15]. The key point of our algorithm is the use of covering codes together with local search. Compared to other “weakly exponential” algorithms, our algorithm is technically quite simple. We also show how to improve the bound above by moderate technical effort. For 3-SAT the improved bound is 1.481n.
UR - http://www.scopus.com/inward/record.url?scp=84974604587&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84974604587
SN - 9783540450221
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 236
EP - 247
BT - Automata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings
A2 - Montanari, Ugo
A2 - Welzl, Emo
A2 - Rolim, Jose D. P.
PB - Springer Nature
T2 - 27th International Colloquium on Automata, Languages and Programming, ICALP 2000
Y2 - 9 July 2000 through 15 July 2000
ER -
