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

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.

• Are you asking for lower bounds for problems or for lower bounds for specific algorithms? Nov 18 '12 at 11:21
• @A.Schulz I'm asking for lower bounds for problems. Nov 18 '12 at 11:36
• @RealzSlaw, right, I've edited the question, now with the standard assumption that $n$ is the size of the input; I've also specified that with centralized I meant "serial", as I've lernt here en.wikipedia.org/wiki/Algorithm#By_implementation Nov 18 '12 at 11:53
• quite interestingly, we don't find much attention given to such classes - as it was done with the sorting problem. Matrix multiplication is $\Omega(n^2)$. The all-shortest path problem is $\Omega(n^2)$ - which you probably already know. But is there a class for these algorithms? I really dont know. The similarity between these problems is that every input (among the $n$) will have to do an action with every other input. Such action is at least $\Omega(1)$.
– AJed
Nov 18 '12 at 13:32
• @RealzSlaw: I agree with you. I lacked some details in my answer. But you understand what I want to say.
– AJed
Nov 18 '12 at 16:29

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

Some simple problems that have lower bounds greater than the size of their inputs, are algorithms that have output sizes greater than their input sizes.

Some examples:

• The problem of listing all solutions to 3-SAT, or similarly, the problem of listing all Hamiltonian cycles. These problems both have exponential number of solutions in the worst case. Thus they have a lower bound of $\Omega (c^n),c>1$. Interestingly however, the 3-SAT problem itself has no known super-linear (greater than $\Omega (n)$) bounds! This means we do not know if it is harder than linear!
• You can even make up new algorithms like this: "completing a graph" that is, given $G = V,E$, where $E=\varnothing$, and $n=|V|$, the algorithm will output a graph $G' = V,E'$, where $E'=\left\{u,v|u\neq v\space\wedge\space u,v\in V \right\}$.

Furthermore, you might be able to compose a problem that has $\Omega (n^2)$-sized outputs, with a problem that takes $\Omega (n^2)$ as input, and outputs $\Omega (n)$ or even $\Omega (1)$-sized outputs (for example, something that counts the number outputs) to obtain a problem that takes $\Omega(n)$-sized input, and outputs $\Omega (n)$-sized output, and yet has a running time greater than $\Omega (n)$. However it might be very difficult to prove (that there is no shortcut to obtain the answer in less time).

Another way some problems have known lower bounds, is to restrict the model of computation.

Though comparison sort's lower bound does not exceed $\Omega (n\log n)$, I think its worth discussing. Comparison sort is also a problem that has a greater lower bound than its input size, but it's lower bound does not exceed $\Omega (n\log n)$, and in . However, as I was researching this, I found this question on mathoverflow: Super-linear time complexity lower bounds for any natural problem in NP. Further examples listed in the answer there are far below $\Omega (n\log n)$. I think the gist of it is, if you restrict the model of computation, you can get lower bounds for problems for which we otherwise do not have them. And if you do not restrict the model of computation, it is very difficult to prove lower bounds on problems.

• There is something I dont understand. Long multiplication can be done with less than O(n^2) according to wikipedia ? Therefore, $\Omega(n^2)$ is nto a lower bound.
– AJed
Nov 18 '12 at 13:20
• Matrix multiplication can be done with $O(n^2.8)$ and this bound has been improved. However, a natural lower bound is $\Omega(n^2)$.
– AJed
Nov 18 '12 at 13:24
• @AJed its not a lower bound on the problem, but its a lower bound on the algorithm. Nov 18 '12 at 14:33
• And now he edited his question to address "problem" instead of algorithm. Nov 18 '12 at 14:34
• @RealzSlaw I apologize for being not enough accurate in the text of my question at the beginning. Nov 18 '12 at 17:39