HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Is there any nontrivial problem in the theory of serial algorithms with a nontrivial polynomial lower bound of $\Omega(n^2)$?

Submitted by: @import:stackexchange-cs··
0
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.

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.)

Context

StackExchange Computer Science Q#6732, answer score: 10

Revisions (0)

No revisions yet.