Yes, the time hierarchy theorem implies the existence of such problems. They're arguably not natural because they involve diagonalizing over all O(n^2)-time algorithms.
Asymptotic lower bound of O(n^2)
-
01-06-2022 - |
문제
Are there problems in P that have a proven asymptotic lower bound of O(n^2) or higher? (n is the number of bits a problem instance can be represented by). This is not a homework question, just curiosity.
해결책
다른 팁
3SUM comes to mind. There's a quadratic lower bound known for a certain linear decision-tree model due to Jeff Erickson. (There are some barely-subquadratic algorithms for 3SUM in the literature for various models of computation. But I haven't looked at them and I don't know how they work.)
제휴하지 않습니다 StackOverflow