Geodesic
On the complexity of unique Circuit SAT
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part X, Tome 475 (2018), pp. 122-136

Voir la notice de l'article provenant de la source Math-Net.Ru

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]. 
@article{ZNSL_2018_475_a5,
     author = {A. A. Lialina},
     title = {On the complexity of unique {Circuit} {SAT}},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {122--136},
     publisher = {mathdoc},
     volume = {475},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2018_475_a5/}
}
TY  - JOUR
AU  - A. A. Lialina
TI  - On the complexity of unique Circuit SAT
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2018
SP  - 122
EP  - 136
VL  - 475
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2018_475_a5/
LA  - en
ID  - ZNSL_2018_475_a5
ER  - 
%0 Journal Article
%A A. A. Lialina
%T On the complexity of unique Circuit SAT
%J Zapiski Nauchnykh Seminarov POMI
%D 2018
%P 122-136
%V 475
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZNSL_2018_475_a5/
%G en
%F ZNSL_2018_475_a5
A. A. Lialina. On the complexity of unique Circuit SAT. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part X, Tome 475 (2018), pp. 122-136. http://geodesic.mathdoc.fr/item/ZNSL_2018_475_a5/