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. ред. / Ugo Montanari; Emo Welzl; Jose D. P. Rolim. Springer Nature, 2000. стр. 236-247 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 1853).
Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Harvard
Dantsin, E, Goerdt, A
, Hirsch, EA & Schöning, U 2000,
Deterministic algorithms for k-SAT based on covering codes and local search. в U Montanari, E Welzl & JDP Rolim (ред.),
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), Том. 1853, Springer Nature, стр. 236-247, 27th International Colloquium on Automata, Languages and Programming, ICALP 2000, Geneva, Швейцария,
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. в U. Montanari, E. Welzl, & J. D. P. Rolim (Ред.),
Automata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings (стр. 236-247). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 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. в Montanari U, Welzl E, Rolim JDP, Редакторы, Automata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings. Springer Nature. 2000. стр. 236-247. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
Author
Dantsin, Evgeny ; Goerdt, Andreas
; Hirsch, Edward A. ; Schöning, Uwe. /
Deterministic algorithms for k-SAT based on covering codes and local search. Automata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings. Редактор / Ugo Montanari ; Emo Welzl ; Jose D. P. Rolim. Springer Nature, 2000. стр. 236-247 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
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 -
