问题来自美人他爹和Wangjianshuo's blog
一个查询的例子：NOT (AND ((C1>5), OR ((C2<6),(C3<>9))))
问题1：给出两个这样的查询Q1和Q2，如何确定Q1的结果是否是Q2结果的子集？
上面两篇文章主要是讨论实际工作中怎么解决问题1。下面从理论上分析一下这个问题。
问题2：判断Q1查询结果是否为空集。
在问题1中让Q2查询结果为空集，故问题1是比问题2更难的一...

PS: PCP可以说是理论计算机领域近20年来的最重要的结果之一，它给了NP问题一个新的刻画，并且提供了一种证明近似算法下界的方法。下面是yijia写的PCP介绍。
作者：yijia
我们可以从最基本的NP开始。一般NP的定义是基于nondeterministic Turing machine，但我们也可以用类似于Interactive Proof的系统来刻画：
一个语言是在NP内当且仅当存在一个多项式时间的算法  (i.e., prover...

上篇文章扫雷是NP完全问题之后，You Xu提到＂不光扫雷是NP 完全问题，空当接龙问题也极有可能是一个NP完全问题。目前最好的通用 planner只能解半副牌＂。他说对了，不光扫雷，Windows自带的游戏都是NP完全的。Windows自带的游戏除了扫雷，还有空当接龙和蜘蛛纸牌。
空当接龙是NP完全问题
论文：Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intell...

本科时有同学扫雷最快可以在60多秒完成高级难度，让我这种最快130秒的人非常惭愧，当时就想着编一个全自动的扫雷程序，不过一直也没写。今天才知道，原来扫雷问题是NP完全的...
结果于2000年发表在Mathematical Intelligencer上，论文题目是Minesweeper is NP-complete，这里有作者的简单的问题和证明介绍。证明方法是证明扫雷问题可以编码任何逻辑电路，包括NP-hard的3SAT问题。...

好久没有写我的理论计算机初步系列了，其实复杂性这一块，虽然平时经常遇到，但由于问题都过于本质和困难，想这方面问题的时间反而不多。Ko教授就跟我说也许NP verse P这个题并不难，只不过大家认为它很难，结果就没有多少人去做了，大家一遇到这个问题都远远得绕开。话虽如此，我还是不敢去碰的。
很多人一看到NP-hard，就从字面上理解成为比NP还难的问题。但...