A note on random k-SAT for moderately growing k

Jun Liu; Zongsheng Gao; Ke Xu

doi:10.37236/1176

A note on random k-SAT for moderately growing k

Jun Liu^*
, Zongsheng Gao
, Ke Xu

^*Corresponding author for this work

School of Computer Science and Engineering

Beihang University

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

5 Scopus citations

Abstract

Consider a random instance I of k-SAT with n variables and m clauses. Suppose that θ, c > 0 are any fixed real numbers. Let k = k(n) ≥ (1/2 + θ) log₂ n.

Original language	English
Journal	Electronic Journal of Combinatorics
Volume	19
DOIs	https://doi.org/10.37236/1176
State	Published - 2012

Keywords

K-SAT
Phase transition
The second moment method

Access to Document

10.37236/1176

Cite this

@article{276d80c7c0714e908f77b4b27e63dec4,

title = "A note on random k-SAT for moderately growing k",

abstract = "Consider a random instance I of k-SAT with n variables and m clauses. Suppose that θ, c > 0 are any fixed real numbers. Let k = k(n) ≥ (1/2 + θ) log2 n.",

keywords = "K-SAT, Phase transition, The second moment method",

author = "Jun Liu and Zongsheng Gao and Ke Xu",

year = "2012",

doi = "10.37236/1176",

language = "英语",

volume = "19",

journal = "Electronic Journal of Combinatorics",

issn = "1097-1440",

publisher = "Australian National University",

}

TY - JOUR

T1 - A note on random k-SAT for moderately growing k

AU - Liu, Jun

AU - Gao, Zongsheng

AU - Xu, Ke

PY - 2012

Y1 - 2012

N2 - Consider a random instance I of k-SAT with n variables and m clauses. Suppose that θ, c > 0 are any fixed real numbers. Let k = k(n) ≥ (1/2 + θ) log2 n.

AB - Consider a random instance I of k-SAT with n variables and m clauses. Suppose that θ, c > 0 are any fixed real numbers. Let k = k(n) ≥ (1/2 + θ) log2 n.

KW - K-SAT

KW - Phase transition

KW - The second moment method

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

U2 - 10.37236/1176

DO - 10.37236/1176

M3 - 文章

AN - SCOPUS:84863050413

SN - 1097-1440

VL - 19

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

ER -

A note on random k-SAT for moderately growing k

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this