可满足性(SAT)问题是一类约束满足问题，它的判定问题是是否存在一组变量的赋值使得命题为真。当K≥3，K-SAT问题是著名的NP完全问题.随机k-SAT问题是这个方向研究的热点，因为人们更关心的是那些典型问题的难易程度。约束密度α是约束数与变量数之比，在随机k-SAT问题中，存在着可满足-不可满足的相变点αs(K)。自旋玻璃中的空腔方法给出了这个相变点的近似值，对于随机3-SAT问题，αs≈4.267。在可满足区域，存在很多高效的启发式算法可以快速找到问题的解，但它们大多是不完全算法，不能证明一个实例不可满足。严格证明一个3-SAT实例不可满足是很困难的，目前虽然存在完全算法，但却不适用与大系统。在不可满足区域，证明不可满足性的难度会随着约束密度增大而减小。　　 在这篇文章中，我们应用统计物理平均场方法，证明当约束密度α＞19时，随机3-SAT问题中存在着一种可以证明其不可满足的证据(Feige-Kim-Ofek证据)，即当α＞19时，这种证据原则上都能被构造出来。然后我们又提出了两种算法在随机的单幅图中构造Feige-Kim-Ofek证据，一种是简单的随机取样算法，一种是局域搜索算法。未经优化的随机取样算法只有当约束密度与变量数N为线性关系时才有效，不过局域搜索算法在约束密度α＞cNb，b≈0.59，c≈8时，都能证明随机3-SAT问题是不可满足的。而且通过增大局域搜索算法中的一个控制参数S，b值能进一步减小。在总结部分，我们还提出了可以进一步改进算法表现的一种思路。