patternModerate
Is there any nontrivial problem in the theory of serial algorithms with a nontrivial polynomial lower bound of $\Omega(n^2)$?
Viewed 0 times
problemnontrivialtheboundomegapolynomialtheorywithanylower
Problem
In the theory of distributed algorithms, there are problems with lower bounds, as $\Omega(n^2)$, that are "big" (I mean, bigger than $\Omega(n\log n)$), and nontrivial.
I wonder if are there problems with similar bound in the theory of serial algorithm, I mean of order much greater than $\Omega(n\log n)$.
With trivial, I mean "obtained just considering that we must read the whole input" and similarly.
I wonder if are there problems with similar bound in the theory of serial algorithm, I mean of order much greater than $\Omega(n\log n)$.
With trivial, I mean "obtained just considering that we must read the whole input" and similarly.
Solution
There are such problems by time hierarchy theorem. Just take any problem that is complete for a large complexity class. For example, take a problem that is complete for $\mathsf{ExpTime}$. Such a problem will be $\Omega(n^c)$ for all $c\in\mathbb{N}$.
However also note that for problems in $\mathsf{NP}$, there are not strong time lower-bounds in multiple-tape TM model and existence of linear time algorithms for SAT is consistent with current state of knowledge. (In single-tape TM model it is not difficult to show that many problems like palindromes require $\Omega(n^2)$ time but such lower-bounds depend essentially on the particulars of the single-tape TM model.)
However also note that for problems in $\mathsf{NP}$, there are not strong time lower-bounds in multiple-tape TM model and existence of linear time algorithms for SAT is consistent with current state of knowledge. (In single-tape TM model it is not difficult to show that many problems like palindromes require $\Omega(n^2)$ time but such lower-bounds depend essentially on the particulars of the single-tape TM model.)
Context
StackExchange Computer Science Q#6732, answer score: 10
Revisions (0)
No revisions yet.