|
Zapiski Nauchnykh Seminarov POMI, 2018, Volume 475, Pages 122–136
(Mi znsl6688)
|
|
|
|
On the complexity of unique Circuit SAT
A. A. Lialinaab a St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences, St. Petersburg, Russia
b Saint Petersburg State University, Saint Petersburg, Russia
Abstract:
We consider the Circuit SAT problem for a circuit with at most one satisfying assignment. We present an algorithm running in time $O(2^{.374589m})$, where $m$ is the number of internal gates of the circuit. In order to make the exposition self-contained, we also describe the algorithm for the general case of Circuit SAT with running time $O(2^{.389667m})$ obtained by Savinov in [10].
Key words and phrases:
unique circuit SAT, circuit SAT, branching heuristics.
Received: 05.12.2018
Citation:
A. A. Lialina, “On the complexity of unique Circuit SAT”, Combinatorics and graph theory. Part X, Zap. Nauchn. Sem. POMI, 475, POMI, St. Petersburg, 2018, 122–136
Linking options:
https://www.mathnet.ru/eng/znsl6688 https://www.mathnet.ru/eng/znsl/v475/p122
|
Statistics & downloads: |
Abstract page: | 92 | Full-text PDF : | 36 | References: | 27 |
|