complexity-theory - 从 A 到 B 的多项式时间减少 - B 至少和 A 一样难

Question

很多次我听说，如果我们可以在多项式时间内将问题 A 简化为问题 B，那么问题 B 至少和问题 A 一样难。这个陈述有多精确？我相信我们应该这样理解:如果A可以被poly-time减少到B，那么如果B有一个poly-time算法，那么它一定存在于A。

我的观点是，与 B - O(n^4) 相比，A 实际上可能比 B 更难(可以具有更高的时间复杂度，例如 O(n^100)，因为减少 poly-time 本身可能很耗时。所以 O(n^4) 和减少所需时间的总和可以给出一个算法 A 将是 O(n^100). 所以每次我读 A 并不比 B 难在这种情况下是不可能的A 没有多项式时间算法而 B 有多项式时间算法。这是正确的吗？

Answer 1

正确的。

一般来说，我会说这个语句中的术语“硬”对应于 complexity class ，不是多项式的次数。或者，更确切地说，问题的“难度”是包含该问题的最小复杂度类。

也就是说，如果 A 至少与 B 一样难，那么 B 的最小复杂度类将被 A 的最小复杂度类取代。