哪些语言是NP完整的？

Question

我正在寻找NP和NP完全问题之间的区别.我在Jason的StackOverflow中找到了这个很棒的答案.关于NP完全问题,他说

NP问题X,在多项式时间内可以减少任何其他NP问题Y到X. 直观地说,这意味着如果我们知道如何快速解决X,我们可以快速解决Y. 确切地说,如果存在多项式时间算法f,则Y可简化为X,以便在多项式时间内将X的实例x转换为Y的实例y = f(x),并且当且仅当答案时,x的答案为是到f(x)是肯定的.

我的问题是:哪一个是NP完全问题,X还是Y？

Answer 1

NP完全语言是X.想法是你可以从任意NP语言Y开始,并在多项式时间内将其减少到X.

形式上,NP完全性的定义如下:语言X称为NP-complete iff

1. X∈NP.也就是说,X不能比"最难的NP问题""更难",因为X本身就是NP的成员.
2. 对于任何Y∈NP,存在从Y到X的多项式时间映射减少.也就是说,X与NP中的任何问题"至少一样难",因为X的多项式时间算法给出了多项式时间算法用于Y的事实,即Y是多项式时间可还原成X有时Y表示≤ _p X,通过的方式.

也就是说,可以将任何NP完全语言简化为任何其他NP完全语言,因此如果Y多项式时间减少到X而X是NP完全,则Y可能(但不是必须)为NP -完成.然而,众所周知,如果Y在多项式时间内减少到X,则Y必须是NP的元素.

希望这可以帮助!