将2sat #P算法结果解算到P=NP中

Question

我在维基百科上读了一篇文章https://en.wikipedia.org/wiki/Sharp-P-complete

并偶然发现了这一行:有多少不同的变量赋值将满足给定的2SAT公式？

有人能链接我一个证明或写一个指出解决2SAT#P算法可以解决任何NP问题的证明吗，因为上面说2SAT#P解决了PvsNP？

Answer 1

如果我没理解错的话，你指的是这一行：

解决#P-完全问题的多项式时间算法，如果存在，将意味着P= NP

在你链接的维基百科页面上。

与你的问题标题的一个重要区别是“多项式时间”部分。一个#p-完全问题的多项式时间解(如#2SAT)将证明P=NP。在时间上不是多项式的解决方案(关于它们的输入)已经存在。(我假设你知道这一点，但我觉得有必要包括这个澄清，这样那些不知道区别和阅读这个问题的人就不会被误导)。

回答你的问题--记住#P是与NP中的决策问题相对应的所有计数问题的类别。现在来自#P Wikipedia page

很明显，#P问题必须至少和相应的NP问题一样难。如果计算答案很容易，那么判断是否有答案也一定很容易--只需对它们进行计数，看看计数是否大于零。

当然，所描述的缩减是在多项式时间内完成的(我们实际上使用完全相同的输入并解决它的计数问题，然后对输出执行一次检查-它是否大于零)。

对于答案的完成(对于那些还不知道的人来说)，这是为什么第一行引用的是真的:如果有一个多项式时间算法来解决#P-complete问题，那么它可以用来在多项式时间内解决所有#P问题，方法是使用从它们到它的多项式时间归约(因为它是一个#P-完全问题而存在)，并用所述算法解决它。从相应的#P问题(如第二个引号)显示任何NP问题的多项式时间缩减意味着，如果存在这样的算法，对于任何NP问题，我们可以查看其计数问题(根据定义在#P中)，将其简化为#2SAT，求解它并获得NP问题的结果-所有这些都是在多项式时间内完成的。这意味着-如果存在这样的算法，所有NP问题都可以使用确定性图灵机在多项式时间内解决，这意味着它们都在P(和P=NP)中。