Research output: Contribution to journal › Article › peer-review
An upper bound O(20.16254n) for exact 3-satisfiability : A simpler proof. / Kulikov, A. S.
In: Journal of Mathematical Sciences , Vol. 126, No. 3, 01.01.2005, p. 1195-1199.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - An upper bound O(20.16254n) for exact 3-satisfiability
T2 - A simpler proof
AU - Kulikov, A. S.
PY - 2005/1/1
Y1 - 2005/1/1
N2 - The exact 3-satisfiability problem (X3SAT) is formulated as follows: given a Boolean formula in 3-CNF, find a truth assignment such that exactly one literal in each clause is set to true. It is well known that X3SAT is NP-complete. In this paper, we present an exact algorithm solving X3SAT in time O(20.162536n), where n is the number of variables. Our proof of this bound is slightly simpler than that of Porschen, Randerath, and Speckenmeyer. These proofs are independent (and algorithms are slightly different), though they are based on the same ideas appeared in the proof of the previous bound O(20.186916n) by the same authors. Bibliography: 6 titles.
AB - The exact 3-satisfiability problem (X3SAT) is formulated as follows: given a Boolean formula in 3-CNF, find a truth assignment such that exactly one literal in each clause is set to true. It is well known that X3SAT is NP-complete. In this paper, we present an exact algorithm solving X3SAT in time O(20.162536n), where n is the number of variables. Our proof of this bound is slightly simpler than that of Porschen, Randerath, and Speckenmeyer. These proofs are independent (and algorithms are slightly different), though they are based on the same ideas appeared in the proof of the previous bound O(20.186916n) by the same authors. Bibliography: 6 titles.
UR - http://www.scopus.com/inward/record.url?scp=17144372944&partnerID=8YFLogxK
U2 - 10.1007/s10958-005-0096-0
DO - 10.1007/s10958-005-0096-0
M3 - Article
AN - SCOPUS:17144372944
VL - 126
SP - 1195
EP - 1199
JO - Journal of Mathematical Sciences
JF - Journal of Mathematical Sciences
SN - 1072-3374
IS - 3
ER -
ID: 49824495