减少3SAT问题:将一个3SAT实例加上一个虚拟变量和一个虚拟子句,即 [原公式] AND (虚拟 OR 非虚拟 OR 虚拟) 。无论虚拟变量的值是什么,它都不会影响公式的计算结果。结果实例的满足方案数量是原实例的两倍,因为每个原始方案在修改后的公式中生成两个方案:一个是虚拟 = 真,另一个是虚拟 = 假。 因此,如果原始实例至少有一个满足方案,则结果实例至少有2个满足方案。