如果有人能够证明 NP 完全问题的指数下限，那会证明 P ≠ NP 吗？
问问题
682 次
2 回答
1
是的，这将证明 P 不等于 NP。所有多项式都以任何指数函数为界，因此任何NP 问题的指数下界将证明问题不在 P 中，从而证明 P 不等于 NP。
希望这可以帮助！
于 2013-11-18T08:25:07.950 回答
0
你是绝对正确的。如果您证明 A 的指数下限，则表明 A 不能位于 P 中。如果 A 确实位于 P 中，它将在多项式时间内是可判定的，这比您刚刚证明的下限渐近更快 - 我们有一个矛盾！
但是，您不必选择 NP 完全问题。您可以在 NP 中选择任何语言 A。通过证明 A 不属于 P，你也证明了 P 不等于 NP。为什么？因为如果 P 确实等于 NP，那么 A 也将位于 P 中，因为我们只是从 NP 中选择了 A。
于 2014-03-24T18:07:54.753 回答