计算机应用与软件
計算機應用與軟件
계산궤응용여연건
COMPUTER APPLICATIONS AND SOFTWARE
2009年
2期
100-102,113
,共4页
随机k-SAT实例%随机扰动模型M(mnk)%最小k-击中集
隨機k-SAT實例%隨機擾動模型M(mnk)%最小k-擊中集
수궤k-SAT실례%수궤우동모형M(mnk)%최소k-격중집
给定一个k-SAT实例F,将作用于公式F得到随机k-SAT实例F′.在随机扰动模型M(m; n; k)下,随机k-SAT实例F′的若干性质.并证实当子句密度足够大时,随机k-SAT实例F′的不可满足性判定可以归结为最小k-击中集问题的求解.
給定一箇k-SAT實例F,將作用于公式F得到隨機k-SAT實例F′.在隨機擾動模型M(m; n; k)下,隨機k-SAT實例F′的若榦性質.併證實噹子句密度足夠大時,隨機k-SAT實例F′的不可滿足性判定可以歸結為最小k-擊中集問題的求解.
급정일개k-SAT실례F,장작용우공식F득도수궤k-SAT실례F′.재수궤우동모형M(m; n; k)하,수궤k-SAT실례F′적약간성질.병증실당자구밀도족구대시,수궤k-SAT실례F′적불가만족성판정가이귀결위최소k-격중집문제적구해.
