如果a可以还原为b，则b poly time可以还原为a吗？

Question

基本上，以下陈述是真的吗？

$ a leq_p b $ $ rightarrow $ $ $ b leq_p a $

Answer 1

简短答案：不。

一个例子，以$ a $为语言$ a = {0，1 }^*$，即包含的语言 每一个 可能的字符串。它几乎可以降低到几乎所有内容，例如3-SAT（还原输出$ x wedge y wedge y wedge z $在每个输入上）。但是3-sat绝对不是$ a $的：没有什么可以映射不满意的实例了。

也许有点愚蠢。以$ a $为$。 $写成二进制，无论$ m $ $ $ halts in $ k $ time Steps of $ x $）。因为$ b $是指数时间的完整，所以$ a $可还原为$ b $。因为从$ b $减少到$ a $将暗示$ b $的多时间算法，因此对于任何指数时间问题，与时间层次定理相矛盾，因此不存在这样的polytime降低。

Answer 2

如果$ a，b $是np-complete，则$ np $中的每个问题都可以还原为$ a $，而polytime则可以还原为$ b $。尤其是$ a $可以还原为$ b $，反之亦然。因此，这回答了NP完整问题的问题。