algorithm - P类语言的线性时间减少，复杂性影响

Question

我在理解 P 和 NP 缩减这个主题时遇到问题。我知道如果语言 L1 可以在线性时间内简化为语言 L2 并且 L2 在 P 中，这意味着 L1 在 P 中。但是如果我们知道 L2 的时间复杂度可以说是 theta(n log n)，我们可以说 L1 在 O(n log n) 中运行？因为从 L1 到 L2 的减少是线性时间，而 L2 在 theta(n log n) 中运行，所以它将是 O(n) + theta(n log n)。并且还可以说 L2 也可以线性减少到 L3，我们可以说 L3 在 omega(n log n) 中运行？

Answer 1

tl;dr:是的。是的，如果你指的是大 Omega。

---

第一部分是正确的:如果你可以在 Theta((n*log(n))) 中决定 L2，这意味着它可以在 O(n*log(n)) 中完成，你可以将 L1 减少到 L2 O(n)，那么您也可以根据您提出的论点在 O(n*log(n)) 中决定 L1。 (注意:这不意味着，你不可能在小于这个的情况下决定 L1 - 可能有一种算法可以在 O(n) 中解决 L1。它只是一个上限...... )

但是，第二部分不正确。如果你可以将 L2 减少到 L3，那么无论从 L2 减少到 L3 的运行时间是多少，你都不能说 L3 的运行时间。(更新:这只表明 L3 可能更难，而不是更多) L3 可能是一个非常困难的问题，例如 SAT。然后很可能您可以将 L2 减少到它，即您可以通过“改写”(减少)问题 + SAT 求解器来解决 L2 - SAT 仍然是 NP 完全的。

---

免责声明:正如 DavidRicherby 在评论中指出的那样，我的回答的第二部分是错误的 - @ uchman21 你是对的，L3 必须在 Omega(n*log(n)) 中(注意大写! ):

如果我们知道 L2 的复杂度是 Theata(n*log(n))(上限和下限，O(n*log(n))和 Omega(n*log(n ))) 并且我们可以在 O(n) 时间内将 L2 减少到 L3，那么 L3 至少和 L2 一样难 - 因为我们知道 没有算法 可以比 Omega 更快地解决问题 L2 (n*log(n))。但是，如果 L3 更快，即在 o(n*log(n)) 中，则算法“reduction+solve_L3”在 O(n)+o(n*log(n)) 中运行，它仍然在 o( n*log(n)) 并且它解决了 L2 - 矛盾。因此，L3 必须在 Omega(n*log(n)) 中。