江西师范大学学报（自然科学版）
江西師範大學學報（自然科學版）
강서사범대학학보（자연과학판）
JOURNAL OF JIANGXI NORMAL UNIVERSITY（NATURAL SCIENCES EDITION）
2011年
2期
111-115
,共5页
MAX k-SAT%上界%一阶矩方法
MAX k-SAT%上界%一階矩方法
MAX k-SAT%상계%일계구방법
对于包含n个变量和m=αn个长度为k的子句的CNF公式,人们比较关注公式中最大可满足子句的个数max Fk(MAX k-SAT).当子句密度α比较大时,随机MAX k-SAT模型中的变量fk(n,αn)(=)(E)(max Fk)的上界可以用一阶矩方法给出.通过对一阶矩方法放缩精度的改进,得到了它的一个更紧的上界(1-1/2k)αn+h(α,t)·αn.同时,可以证明这个新的上界随着t的增大而变得更紧.
對于包含n箇變量和m=αn箇長度為k的子句的CNF公式,人們比較關註公式中最大可滿足子句的箇數max Fk(MAX k-SAT).噹子句密度α比較大時,隨機MAX k-SAT模型中的變量fk(n,αn)(=)(E)(max Fk)的上界可以用一階矩方法給齣.通過對一階矩方法放縮精度的改進,得到瞭它的一箇更緊的上界(1-1/2k)αn+h(α,t)·αn.同時,可以證明這箇新的上界隨著t的增大而變得更緊.
대우포함n개변량화m=αn개장도위k적자구적CNF공식,인문비교관주공식중최대가만족자구적개수max Fk(MAX k-SAT).당자구밀도α비교대시,수궤MAX k-SAT모형중적변량fk(n,αn)(=)(E)(max Fk)적상계가이용일계구방법급출.통과대일계구방법방축정도적개진,득도료타적일개경긴적상계(1-1/2k)αn+h(α,t)·αn.동시,가이증명저개신적상계수착t적증대이변득경긴.
