如果问题 X 简化为问题 Y，是否也可以进行相反的简化？说
X = 给定一个数组，判断所有元素是否不同
Y = 使用比较排序对数组进行排序
现在，X 在线性时间内减少到 Y，即如果我可以解决 Y，我可以在线性时间内解决 X。反过来总是正确的吗？如果我能解决 X，我能解决 Y 吗？如果是这样，怎么做？
减少我的意思是：
Problem X linear reduces to problem Y if X can be solved with:
a) Linear number of standard computational steps.
b) Constant calls to subroutine for Y.
假设我可以在恒定时间 O(1) 内解决问题 A，但问题 B 的最佳情况是指数时间解 O(2^n)。我很可能会想出一种非常复杂的方法来解决 O(2^n) 中的问题 A（“减少”问题 A 到 B），但是如果您的问题的答案是“是”，那么我应该能够在 O(1) 中解决所有极其困难的问题。当然，这不可能！
鉴于上面的例子：
O(N)如果您使用哈希表备份它们，您可以确定所有元素是否不同。这允许您检查是否存在O(1)+ 散列函数的开销（这通常无关紧要）。如果您正在进行基于非比较的排序：
为简单起见，假设您正在对自然数列表进行排序。使用未煮过的意大利面条棒来说明排序方法：对于列表中的每个数字 x，获取长度为 x 的棒。（选择单位的一种实用方法是让列表中的最大数字 m 对应于一整条意大利面。在这种情况下，整条意大利面等于 m 个意大利面单位。要获得长度为 x 的杆，只需折断一根杆一分为二，其中一个长度为 x 个单位；丢弃另一块。）
准备好所有的意大利面棒后，将它们松松地握在拳头中，然后将它们放到桌子上，使它们都直立，放在桌面上。现在，对于每根棍子，将另一只手从上方放下，直到碰到一根棍子——这显然是最长的！移除此杆并将其插入（最初为空）输出列表的前面（或等效地，将其放置在输出数组的最后一个未使用的插槽中）。重复直到所有的棒都被移除。
因此，鉴于您的问题的一个非常专业的案例，您的陈述将成立。但是，这在一般情况下并不成立，这似乎更符合您的要求。这与人们认为他们已经解决了 TSP 的情况非常相似，但实际上他们创建了一个可以使用特殊算法解决的一般问题的受限版本。
假设我理解减少的意思，假设我有一个问题可以O(N)通过使用键/值对数组来解决，即从列表中查找内容的问题。O(1)我可以通过使用字典来解决同样的问题。
这是否意味着我可以回到我的第一个技术，并用它来解决同样的问题O(1)？
我不这么认为。