在其他类型的减少情况下，P和NP是否有完全的问题？

Question

我知道复杂性类$ mathsf {p} $有完整的问题WRT $ MATHSF {NC} $和$ MATHSF {L} $降低。

这两个类是$ mathsf {p} $的唯一可能的减少类别的类别吗？

另外，在多项式时间降低旁边，可以将哪些类别的减少用于$ mathsf {np} $？

Answer 1

您的问题包含一些不正确或不清楚的短语。 “复杂性X类减少”也不是“我们可以将Y可以减少用于复杂性X类”是有道理的。此外，至少有两个以“多项式降低”的名称为“多项式降低”的定义，它们都用于研究NP完整性：多项式时间多一减少和多项式时间的Turing减少。但是，在这个答案中，我将忽略许多减少和图灵减少之间的区别，而我只专注于减少的资源限制，因为否则答案将变得太长且没有重点。

现在，我将重申您可能想问的内容，并回答它们。

除多项式时间降低以外，是否可以定义NP完整性的减少定义？除了NC降低和日志空间降低外，还可以定义p完整性的降低定义吗？

正如Artem和Raphael所说，您可以定义自己喜欢的任何东西。

除多项式时间降低以外，是否有任何用于研究文献中NP完整性的降低的定义？除NC降低和降低对数空间外，是否有任何用于研究文献中P完整性的减少的定义？

是的。例如，Papadimitriou在整个教科书[Pap94]中使用日志空间减少，包括NP完整性的定义。 （注意：在[Pap94]中，术语“ l-reduction”是指与降低日志空间完全不同的东西。）至于p完整性，nc^k GHMRSS00]中提到了减少。这是NC减少的特殊情况，比对数空间的缩小更一般的情况 k≥2.

但是它们真的是不同的概念，还是同一概念的不同定义？

目前，没人知道。例如，当且仅当l = p时，对数空间的降低性和多项式时间的降低性是等效的。

GHMRSS00] Raymond Greenlaw，H。JamesHoover，Satoru Miyano，Walter L. Ruzzo，Shuji Shiraishi和Takayoshi Shoudai。 平行计算项目：卷I – III, 2000. http://www.cs.armstrong.edu/greenlaw/research/parallel/

Pap94] Christos H. Papadimitriou。 计算复杂性. 。 Addison-Wesley，1994年。

Answer 2

请注意，如果复杂性类别$ c $在一类减少$ a $下有一个完整的问题，那么对于$ c $，$ c $和包含$ a $的缩短类别将完成相同的问题。

通常，完整性证明的减少类别比通常说明的较弱（例如$ Mathsf {ac^0} $降低）。任何包含$ mathsf {ac^0} $的减少类都足够，并且有许多此类类别。

您可能还需要检查以下论文：

• Agrawal，M，Allender，E.，Impagliazzo，R.，Pitassi，T。和Rudich，S。，”降低降低的复杂性”，《计算复杂性杂志》，第10页，第117-138页，2001年。ACMSTOC论文集的初步版本，2001年。

Answer 3

正如Artem在他的 评论, ，问题是无意义的，因为您可以定义自己喜欢的任何东西。让我说明事物开始在哪里“有点愚蠢”。

一些符号：对于两个问题$ p，q $，写$ p p leq_f q $对于某些类函数$ f $，如果f $中有$ f ，则$ p（x）= q（f（x） ）$对于所有输入$ x $（of $ p $），也就是说，如果$ p $可以是$ f $降至$ q $。写$ xc_f $对于$ x $ - complete问题的$ f $，就是

$ qquad displaystyle xc_f = {p in x mid forall q inx。 q leq_f p } $。

此外，用$ t_x $表示算法的（渐近最佳）运行时函数集合在某些$ x $中计算功能的算法。

现在考虑一个任意（复杂性）的问题$ x $ 1。如果我们在时间复杂性方面限制了减少空间$ f $ - 这里的一切皆有可能 - 大约有两种情况：

• $ t_f supseteq omega（t_x）$²-减少速度并不比问题解决者快。

  在这种情况下，$ xc_f = x $ - 对于复杂性理论而言，这显然不是很有趣。考虑到这种$ f $在实践中可能很有用，尤其是如果$ t_f subseteq theta（x）$；您可以将$ x $中的所有问题减少到一些您可以很好地解决的问题。线性编程和SAT是典型的示例，因为高度优化的LP-Resp。卫星赛车。

• $ t_f subseteq o（x）$ - 减少速度比问题解决者快

  在这里可能会发生有趣的事情，即$ xc_f subset x $或$ xc_f neq xc_ {f'} $用于不同的减少空间。这些事实是否具有有趣的后果取决于$ x $和$ f $的具体选择。请注意，$ xc_f = emptyset $可能会发生，这本身就足够有趣。

  当您选择$ f $时，事情肯定会变得不感兴趣，因此“小”，$ leq_f $稀疏，这是可能的减少。想想$ x = mathsf {np} $和$ f $，这样$ t_f subseteq o（n）$;减少必须大量收缩输入尺寸，并且不能花费太多时间，因此$ f $不是很强大。

  但是请注意，即使限制了$ t_f subseteq o（1）$也会留下有意义的关系；例如，“ $ x $是整数吗？”可以简化为“ $ x $的第一个位0？”在$ o（1）$时间和空间中。因此，即使研究如此薄弱的减少，也可能会很有趣，以找出哪些问题与降低复杂性方面的其他问题接近哪些问题。您肯定会在经典$ mathsf {npc} = mathsf {np} c_p $降低中看到这种差异。

从技术上讲，有第三种情况，例如$ t_f = p $和$ t_x = theta（n^3）$;在这种情况下 - 如果$ f $相当丰富 - 对案例一的评论适用。还要注意，哪种情况$ f $属于的问题本身可能很有趣：“ $ mathsf {p = np} $？”本质上是在询问$ t_f = theta（x）$（甚至$ f = theta（xc_f）$）。

---

1. 为了成为“适当”的复杂性类别，它必须是某种“向下封闭” WRT复杂性。
2. $ circ（x）$用于函数类$ x $和$ circ $ a dandau符号是通常的landau符号的自然扩展，即$ circ（x）= bigcup_ {f in x} circ （f）$。