利用极小不可满足公式的临界特性,可以将任意一个3-CNF公式多项式时间归约转换为一个正则（3,4）-CNF公式,从而得到一个保留NP完全性的正则（3,4）-SAT问题。对于归约转换后的正则（3,4）-SAT实例集而言,警示传播算法（Warning Propagation,WP）在其上高概率收敛,然而难以有效地返回关于变元的一组真值指派（如果该实例可满足）。因此,在归约转换下的正则（3,4）-SAT问题上,WP算法求解失效。本文围绕该问题,基于归约转换下正则（3,4）-CNF公式的结构特征,提出了WP算法的一种修正策略来专门用于求解归约转换下的正则（3,4）-SAT实例。同时基于WP算法的信息传播机制,引出了WP-可解公式的结构定义,探索了WP算法的收敛性特征条件。主要的研究成果如下:（1）从三个方面比较了归约转换后的正则（3,4）-CNF公式与原3-CNF公式在公式的结构特征上所发生的变化:一是归约转换后的正则（3,4）-CNF公式中变元正负出现次数之差趋于稳定;二是归约转换后的正则（3,4）-CNF公式中每个变元至少被包含在两个圈中;三是一个归约转换后且可满足的正则（3,4）-CNF公式中至少含有规模大小为9m的脊梁（m为原3-CNF公式子句数）。（2）在WP算法求解随机3-SAT实例集的实验中,发现随着子句约束密度的增大,WP算法会高概率地收敛于平凡稳定点,这意味着算法在初始迭代求解时只能以随机的方式来给变元赋值,从而对算法求解SAT问题的性能造成了影响。因此提出了一种基于最大极性变元的策略来改进WP算法。实验结果表明:改进的WP算法比原算法求解效果更好。（3）针对WP算法在归约转换下且可满足的正则（3,4）-SAT实例集上求解失效的问题,基于归约转换下正则（3,4）-CNF公式中变元正负出现次数趋于稳定的结构特征,提出了WP算法的一种修正策略。实验结果表明:修正的WP算法可以重新有效求解归约转换下的正则（3,4）-SAT实例集。（4）证明了树公式是WP-可解公式。进一步,基于植入分布模型P_n,p^plant,证明了以WP-可解的3-CNF公式作为输入,WP算法高概率收敛。