具有独特解决方案的3SAT公式数量的渐近界

Question

如果包含任何给定的字符串长度$ n $的多项式界数的字符串数，则稀疏。所有已知的NP完整组都很致密。事实证明，当且仅当存在一个稀疏的NP完整集（在KARP降低下）时，P = NP。

我想找到唯一令人满意的3sat公式的密度。它是超多态性密度还是指数密度？关于具有独特溶液的3SAT公式数量的渐近下限有什么了解的？

Answer 1

正如人们所期望的那样，它是密集的。

具有$ n $变量和$ n $条款的唯一令人满意的3SAT公式的数量至少为$ 2^n $，因为对于$ n $变量的每项可能任务，至少有一个3sat公式$ phi $是令人满意的作业，并且有$ 2^n $此类作业。具有$ n $变量和$ n $条款的3SAT实例可以表示为长度$ ell = 3n lg n $的字符串。因此，此类公式的数量为$ ell $。