第12章处理难解问题的策略,12.1对问题施加限制12.1.1二元可满足性问题12.1.2霍恩公式可满足性问题12.2固定参数算法12.3改进指数时间算法12.4启发式方法12.5平均情形的复杂性12.6难解算例生成12.6.1相变现象与难解性12.6.2隐藏解的难解算例,第12章处理难解问题的策略,12.7基于统计物理的消息传递算法12.7.1消息传递与回溯法、局部搜素算法的比较12.7.2基于统计学的消息传递算法12.8量子算法简介12.8.1量子比特12.8.2正交测量12.8.3量子门12.8.4一个量子算法,二元可满足性问题,二元合取范式：合取范式的每一个简单析取式最多只有2个文字二元可满足性：限制SAT实例中的合取范式为2元合取范式设2元合取范式F有n个变元x1,x2,xn和m个简单析取式C1,C2,Cm,每个Cj至多有2个文字.例子：C1=x1x2,C2=x1,C3=x1x2,C4=x2,C5=x3x4,C6=x3x4,C7=x3x4.存在多项式时间的2SAT算法，2SATP,2SAT算法,如果存在只有一个文字的简单析取式Cj，则先进行化
