精华区文章阅读

发信人: ssos (存在与虚无), 信区: Algorithm
标  题: 杉扑阈约蛎鞲僖�(10)
发信站: 哈工大紫丁香 (2001年06月14日15:43:48 星期四), 站内信件

定义 Bool变量或其否定称为文字,简单析取式称为子句或简称句,
合析范式称为子句集合.
SAT问题任给一子句集合,判定可满足性.
Cook-Levin定理 SAT问题属于NPC.
注解这是历史上第一个找到的NPC问题.
定理以下所列问题均为NPC问题.
SAT-3问题任给一子句集合,每个文字只出现在三个子句中,判定
可满足性.
3-SAT问题任给一子句集合,每个子句含有三个字,判定可满足性.
3-SAT-3问题任给一子句集合,每个子句含有三个字,且每个文字只
出现在三个子句中,判定可满足性.
Blocking Set问题任给一集合族,任给整数k,判定存在k个元素,
含于族内所有集合中.

--


<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]

Algorithm 版 (精华区)