A novel weighting scheme for random k-SAT

Jun Liu; Ke Xu

doi:10.1007/s11432-016-5526-8

A novel weighting scheme for random k-SAT

Jun Liu
, Ke Xu^*

^*Corresponding author for this work

School of Computer Science and Engineering

Beihang University

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

Consider a random k-conjunctive normal form F_k(n, rn) with n variables and rn clauses. We prove that if the probability that the formula F_k(n, rn) is satisfiable tends to 0 as n→∞, then r ⩾ 2.83, 8.09, 18.91, 40.81, and 84.87, for k = 3, 4, 5, 6, and 7, respectively.

Original language	English
Article number	92101
Journal	Science China Information Sciences
Volume	59
Issue number	9
DOIs	https://doi.org/10.1007/s11432-016-5526-8
State	Published - 1 Sep 2016

Keywords

complexity
phase transition
satisfiability
second moment method
weighting scheme

Access to Document

10.1007/s11432-016-5526-8

Cite this

@article{954f0dfd36b647adb311ec01dd013666,

title = "A novel weighting scheme for random k-SAT",

abstract = "Consider a random k-conjunctive normal form Fk(n, rn) with n variables and rn clauses. We prove that if the probability that the formula Fk(n, rn) is satisfiable tends to 0 as n→∞, then r ⩾ 2.83, 8.09, 18.91, 40.81, and 84.87, for k = 3, 4, 5, 6, and 7, respectively.",

keywords = "complexity, phase transition, satisfiability, second moment method, weighting scheme",

author = "Jun Liu and Ke Xu",

note = "Publisher Copyright: {\textcopyright} 2016, Science China Press and Springer-Verlag Berlin Heidelberg.",

year = "2016",

month = sep,

day = "1",

doi = "10.1007/s11432-016-5526-8",

language = "英语",

volume = "59",

journal = "Science China Information Sciences",

issn = "1674-733X",

publisher = "Science China Press ",

number = "9",

}

TY - JOUR

T1 - A novel weighting scheme for random k-SAT

AU - Liu, Jun

AU - Xu, Ke

PY - 2016/9/1

Y1 - 2016/9/1

N2 - Consider a random k-conjunctive normal form Fk(n, rn) with n variables and rn clauses. We prove that if the probability that the formula Fk(n, rn) is satisfiable tends to 0 as n→∞, then r ⩾ 2.83, 8.09, 18.91, 40.81, and 84.87, for k = 3, 4, 5, 6, and 7, respectively.

AB - Consider a random k-conjunctive normal form Fk(n, rn) with n variables and rn clauses. We prove that if the probability that the formula Fk(n, rn) is satisfiable tends to 0 as n→∞, then r ⩾ 2.83, 8.09, 18.91, 40.81, and 84.87, for k = 3, 4, 5, 6, and 7, respectively.

KW - complexity

KW - phase transition

KW - satisfiability

KW - second moment method

KW - weighting scheme

UR - https://www.scopus.com/pages/publications/84984871088

U2 - 10.1007/s11432-016-5526-8

DO - 10.1007/s11432-016-5526-8

M3 - 文章

AN - SCOPUS:84984871088

SN - 1674-733X

VL - 59

JO - Science China Information Sciences

JF - Science China Information Sciences

IS - 9

M1 - 92101

ER -

A novel weighting scheme for random k-SAT

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this