随机k-SAT公式不可满足性VS最小k-击中集

• 作者: 杨智应
• 来源期刊: 计算机应用与软件
• 学科: 工学
• 关键词: 随机k-SAT实例 随机扰动模型M(mnk) 最小k-击中集
• 年，卷（期）: 2009,（2）
• 所属期刊栏目: 基金项目基金
• 页码范围: 100-102,113
• 页数: 4页
• 分类号: TP3
• 字数: 3293字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-386X.2009.02.034

摘要

给定一个k-SAT实例F,将作用于公式F得到随机k-SAT实例F′.在随机扰动模型M(m; n; k)下,随机k-SAT实例F′的若干性质.并证实当子句密度足够大时,随机k-SAT实例F′的不可满足性判定可以归结为最小k-击中集问题的求解.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨智应	上海海事大学计算机科学与工程系	29	82	5.0	8.0