所谓合取范式，就是一种所有子句都由合取（即“与”）联接所构成的公式，如"a & (!b | c) & (a | !c | d)"。
这里的“子句”是指一个或多个"文字"的析取，而“文字”就是变量或变量的非。如上式中的“a”，“(!b | c)”和“(a | c | d)”就是“子句”，组成子句的a, !b, c, !c, d就是“文字” ，a, b, c, d就是“变量”。
“3合取范式”就是每个子句恰好由3个文字所组成的合取范式。

举个例子：小红，小王，小江等n人想找个地方去做运动，他们觉得这个地方可能会有m种情况。为了尽量满足所有人的癖好，每个人都根据可能出现的情况提了一个包含3个需求的列表：小红想找个“有窗户”或者“有厕所”或者“没臭味”的地方，小王想找个“没窗户”或“有臭味”或“没厕所”的地方，小江想找个“有厕所”或“没臭味”或“没窗户”的地方。。。问，是否存在一个地方可以满足所有人的（至少一个）要求？
其中，每个人提的需求列表就是一个“子句”，比如小红提的 " '有窗户'或'有大床'或'没臭味' " 就是一个“子句”。
需求列表中的每一项具体的需求都是一个“文字”，比如“有窗户”就是一个文字，“没臭味”也是一个文字。
需求的选项(可能出现的情况)就是“变量”，比如“窗户”就是一个变量，“厕所”是一个变量，“臭味”也是一个变量。
如果最后找到了一个“有窗户，没厕所，没臭味”的地方，那么“有窗户，没厕所，没臭味”就是变量的真值赋值。
所有人需求就是合取范式，如果“每个人的需求都有3项且至少要满足1项”就是“3合取范式”。
3SAT问题就是问 "是否存在"一个满足所有人需求的地方。

为啥要研究这么个奇葩的问题？因为3SAT是一个非常著名的NP完全问题：除非“P=NP”，否则找不到一个多项式复杂度的算法求解这个问题。
有人就问了：“有名就了不起吗？有啥用啊？”
当然有用了，比方你老板要你解决某个问题X，要是你不能又快又准的解出来他就会发飙。如果你能证明这个问题X比3SAT问题还“难”，那么X就也不可能找到一个多项式复杂度的算法来求解。然后你就可以把这个证明甩到你老板脸上：我做不到，别人TMD也做不到！

感谢楼主

举一个例子，想证明3-coloring（三着色）问题是NP，就可以通过将该问题“归约"为3-SAT来证明。
图着色问题：给定一个无向图G=(V,E)，其中V为顶点集合，E为边集合，图着色问题即为将V分为K个颜色组，每个组形成一个独立集，即其中没有相邻的顶点。K=3时，即为3着色问题。
这里的归约的含义为：任意一个3-SAT问题的实例都可以用找到一个3-coloring实例与之对应。举例解释：任意一个乘方运算n^2都能用一个乘法运算n*n与之对应，所以说明乘法运算不比乘方运算简单。

直观理解，可满足性问题就是问是否存在一个可满足实例的问题

你可真行...

那么如何归约呢? 一个常用的方法就是构造，我们可以通过构造出一类具有特殊结构的实例，让所有3SAT的实例都能在多项式时间内转换为该类实例。 比方说3着色问题，就可以通过构造出具有特殊拓扑结构的且满足3着色约束的实例。然后证明所有的3-sat问题的实例都能很容易转换为该类"特殊的"实例。
这样连3SAT这样NP困难的问题都只是3着色问题的一种“特殊”情况，那当然3着色问题不会比3SAT更简单了。

楼主牛逼！

感谢大佬

牛逼

那么如何构造这一类特殊的实例呢？首先必须知道问题是什么。这就得对问题进行严格正式的定义：以3着色问题为例，如何进行形式化定义呢？可以分为两步：
一，问题的解是什么？3着色问题的解就是每个节点的颜色（不超过3种），比如：每个节点颜色可以是 {1，2，3} 中的一个。当然这些节点的颜色必须满足3着色问题中的要求。这里，问题的解又叫做“证书”（Certificate）或者“见证”（witness）。
二，问题是什么？3着色问题恰好是个判定问题（decision problem）：判断是否对于图G的每条边（u，v），节点u的颜色和节点v的颜色不一样：意思是如果每条边上的两个节点的颜色都不一样，那么问题为真，否则为假。这里，问题又被称为“Certifier”或者“Verifier”（验证者），意思是你需要验证问题是否为真。

很显然，问题和问题的解的关系就是：解使得问题为真。