NP完整的等效类是吗？

Question

因此，“ NP完整”有多个可能的定义，其中两个是：

1. 决策问题$ l $是np-commette，仅当且仅当时：$ l in text {np} $和$ forall l' in text {np}：l' preceq_ {p} l $

2. 决策问题$ l $是np-Complete，仅当且仅当：$ l in text {np} $中，并且存在一个np-complete问题$ l in text {np} $ in text {np} $，这样prepeq_ {p} l $

我的问题是，为什么这两个定义等效或换句话说，（为什么）np complete是等效类？

如果这是等价类，我可以理解上述两个定义的等效性，但是我看不到为什么是这种情况，因为（一对多的）poly dime降低$ prepeq_ {p} $不是对称的...： - //

Answer 1

第二个定义是无效的，因为它是自指的。给定第一个定义，第二个语句是第一个定义遵循的简单定理。

确实，假设我们使用第一个定义定义了NP完整性。让我们看看第二个定义是正确的。

$ longrightArrow $如果$ l $是np complete，那么对于所有$ l'$ in in np，$ l'$降低到$ l $。特别是，SAT减少到$ L $。由于SAT由Cook的定理NP完成，因此存在一个NP完整的问题$ L'$（即SAT），该问题将减少到$ L $。

$ longleftarrow $假设$ l $在NP中，一些NP完整问题$ l'$减少到$ L $。我们将证明 每一个 问题$ m $ NP减少到$ L $，因此$ l $是NP完整的。考虑到NP的问题$ m $，因为$ l'$是NP-Complete，因此$ m $减少到$ L'$。由于$ l'$减少到$ l $，因此$ m $也将其减少到$ l $，我们完成了。

证明使用的两个属性：（1）存在一些NP完整问题，（2）降低性是传递性的：如果$ a $还原为$ b $，而$ b $则将$ b $还原为$ c $，然后$ a $降低至$ c $。

最后，任何两个NP完整问题彼此减少（通过定义），从这个意义上讲，它们形成了还原关系的等效类别。