RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. 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.

UDC: 510.52

Received: 05.12.2018

Language: English



© Steklov Math. Inst. of RAS, 2025