class P 中语言的线性时间减少，复杂性影响
Linear time reduction of languages in class P, complexity implications
我在理解 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)?
中运行
tl;dr: 是的。是的，如果你指的是大 Omega。
第一部分是正确的：如果你可以在 Theta((n*log(n))) 中决定 L2，这意味着它可以在 O(n*log(n)) 中完成，你可以将 L1 减少到L2 in O(n)，那么您也可以根据您所做的论点在 O(n*log(n)) 中决定 L1。 （注意：这确实 not 意味着，你不可能在小于这个的情况下决定 L1 - 可能有一种算法可以在 O(n) 中解决 L1。它只是一个上限...)
但是，第二部分不正确。如果你可以将 L2 减少到 L3，那么无论从 L2 减少到 L3 的 运行 时间是多少，你都可以不用说 L3s 运行 时间。（更新：仅此表明 L3 可能更难，而不是更多）L3 可能是一个非常难的问题，例如 SAT。然后很可能你可以将 L2 减少到它，即你可以用 'rephrasing'（减少）问题 + SAT 求解器来解决 L2 - SAT 仍然是 NP-complete。
免责声明：正如 DavidRicherby 在评论中指出的那样，我的回答的第二部分是错误的 - @ uchman21 你是对的，L3 必须在 Omega(n*log(n)) 中（注意上部案例！）：
如果我们知道L2的复杂度是Theata(n*log(n))(上下界,O(n*log(n))andOmega( n*log(n))) 并且我们可以在时间 O(n) 中将 L2 减少到 L3，那么 L3 至少和 L2 一样难 - 因为我们知道 没有算法 可以比Omega(n*log(n))更快的解决问题L2。但是，如果 L3 更快，即在 o(n*log(n)) 中，则算法 'reduction+solve_L3' 在 O(n)+o(n*log(n)) 中运行，它仍然在 o( n*log(n)) 并且它解决了 L2 - 矛盾。因此，L3 必须在 Omega(n*log(n)).
我在理解 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)?
中运行tl;dr: 是的。是的，如果你指的是大 Omega。
第一部分是正确的：如果你可以在 Theta((n*log(n))) 中决定 L2，这意味着它可以在 O(n*log(n)) 中完成，你可以将 L1 减少到L2 in O(n)，那么您也可以根据您所做的论点在 O(n*log(n)) 中决定 L1。 （注意：这确实 not 意味着，你不可能在小于这个的情况下决定 L1 - 可能有一种算法可以在 O(n) 中解决 L1。它只是一个上限...)
但是，第二部分不正确。如果你可以将 L2 减少到 L3，那么无论从 L2 减少到 L3 的 运行 时间是多少，你都可以不用说 L3s 运行 时间。（更新：仅此表明 L3 可能更难，而不是更多）L3 可能是一个非常难的问题，例如 SAT。然后很可能你可以将 L2 减少到它，即你可以用 'rephrasing'（减少）问题 + SAT 求解器来解决 L2 - SAT 仍然是 NP-complete。
免责声明：正如 DavidRicherby 在评论中指出的那样，我的回答的第二部分是错误的 - @ uchman21 你是对的，L3 必须在 Omega(n*log(n)) 中（注意上部案例！）：
如果我们知道L2的复杂度是Theata(n*log(n))(上下界,O(n*log(n))andOmega( n*log(n))) 并且我们可以在时间 O(n) 中将 L2 减少到 L3，那么 L3 至少和 L2 一样难 - 因为我们知道 没有算法 可以比Omega(n*log(n))更快的解决问题L2。但是，如果 L3 更快，即在 o(n*log(n)) 中，则算法 'reduction+solve_L3' 在 O(n)+o(n*log(n)) 中运行，它仍然在 o( n*log(n)) 并且它解决了 L2 - 矛盾。因此，L3 必须在 Omega(n*log(n)).