0

P 中是否存在已证明渐近下界为 O(n^2) 或更高的问题？（n 是问题实例可以表示的位数）。这不是作业问题，只是好奇。

4

2 回答 2

6

是的，时间层次定理暗示了这些问题的存在。它们可以说是不自然的，因为它们涉及对所有 O(n^2) 时间算法的对角化。

于 2013-06-22T19:12:31.207 回答
2

我想到了3SUM。由于 Jeff Erickson，某个线性决策树模型有一个已知的二次下界。（文献中有一些用于各种计算模型的 3SUM 的几乎次二次算法。但我没有看过它们，也不知道它们是如何工作的。）

于 2013-06-23T08:35:23.653 回答