An upper bound O(20.16254n) for exact 3-satisfiability › Научные исследования в СПбГУ

Standard

An upper bound O(2^0.16254n) for exact 3-satisfiability : A simpler proof. / Kulikov, A. S.

в: Journal of Mathematical Sciences , Том 126, № 3, 01.01.2005, стр. 1195-1199.

Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование

Author

Kulikov, A. S. / An upper bound O(2^0.16254n) for exact 3-satisfiability : A simpler proof. в: Journal of Mathematical Sciences . 2005 ; Том 126, № 3. стр. 1195-1199.

BibTeX

@article{f1962e8c7ad347ad9b84d7217c08ac68,

title = "An upper bound O(20.16254n) for exact 3-satisfiability: A simpler proof",

abstract = "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.",

author = "Kulikov, {A. S.}",

year = "2005",

month = jan,

day = "1",

doi = "10.1007/s10958-005-0096-0",

language = "English",

volume = "126",

pages = "1195--1199",

journal = "Journal of Mathematical Sciences",

issn = "1072-3374",

publisher = "Springer Nature",

number = "3",

}

RIS

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

An upper bound O(20.16254n) for exact 3-satisfiability: A simpler proof

Standard

Harvard

APA

Vancouver

Author

BibTeX

RIS

An upper bound O(2^0.16254n) for exact 3-satisfiability: A simpler proof