密集的NP完整语言意味着P = NP

Question

我们说语言$ j subseteq sigma^{*} $是 稠密 如果存在一个多项式$ p $，以便$$ | j^c cap sigma^n | leq p（n）$$用于 in mathbb {n}的所有$ n 。 $

我目前正在研究的问题要求显示以下

如果存在密集的$ np $ -complete语言，则$ p = np $

文本的建议是考虑将多项式减少到$ 3 $ - $ SAT $，然后构建一种算法，该算法试图满足给定的$ CNF $公式，同时也以$ j^c产生元素。

我想知道的是

有更直接的证据吗？这个概念在更一般的环境中是否知道？

Answer 1

这是关于Mahaney定理的一个很好的作业问题。

请注意，“密集”语言的补充是一种稀疏的语言。此外，如果一种语言为$ Mathsf {np} $ - 完成其补充是$ Mathsf {Conp} $ - 完成。

如果有一个“密集” $ mathsf {np} $ - 完整的语言，则有一个 疏 $ mathsf {conp} $ - 完整的语言。

Mahaney的定理告诉我们，除非$ Mathsf {p} = Mathsf {np} $，否则没有稀疏$ mathsf {np} $ - 完整的语言。

我们可以采用证据来证明没有稀疏的$ mathsf {conp} $ - 完整的语言，除非$ mathsf {p} = mathsf {conp} $，它等同于$ mathsf {p} = mathsf { np} $（因为$ mathsf {p} $在补语下关闭）。

总而言之，除非$ mathsf {p} = mathsf {np} $，否则答案是否。请注意，如果$ mathsf {p} = mathsf {np} $，则每个非平地语言都是$ Mathsf {np} $ - 完整。

PS：您可能需要尝试以下内容，然后使用Mahaney的定理：有一个稀疏的$ Mathsf {np} $ - 完整的设置Iff有一个稀疏的$ Mathsf {Conp} $ - 完整集。但是，我怀疑该声明的证明会比Mahaney定理的证明要容易得多。

Answer 2

如上所述 Mahaney的定理. 。除非$ p = np $，否则稀疏和密集的语言不能为$ np-hard $。

提到的草稿包含完整的证明。