|
Zapiski Nauchnykh Seminarov POMI, 2002, Volume 293, Pages 118–128
(Mi znsl1678)
|
|
|
|
This article is cited in 8 scientific papers (total in 8 papers)
An upper bound $O(2^{0.16254n})$ for Exact 3-Satisfiability: a simpler proof
A. S. Kulikov Saint-Petersburg State University
Abstract:
The exact $3$-satisfiability problem (X3SAT) is: 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(2^{0.162536n})$, where $n$ is the number of variables. Our proof of this bound is slightly simpler than one 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(2^{0.186916n})$ by the same authors.
Received: 15.12.2002
Citation:
A. S. Kulikov, “An upper bound $O(2^{0.16254n})$ for Exact 3-Satisfiability: a simpler proof”, Computational complexity theory. Part VII, Zap. Nauchn. Sem. POMI, 293, POMI, St. Petersburg, 2002, 118–128; J. Math. Sci. (N. Y.), 126:3 (2005), 1195–1199
Linking options:
https://www.mathnet.ru/eng/znsl1678 https://www.mathnet.ru/eng/znsl/v293/p118
|
Statistics & downloads: |
Abstract page: | 219 | Full-text PDF : | 94 |
|