Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 4 down vote favorite
1

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

EDIT: with trivial I mean "obtained just considering that we must read the whole input" and similarly.

share|improve this question
Are you asking for lower bounds for problems or for lower bounds for specific algorithms? – A.Schulz Nov 18 '12 at 11:21
@A.Schulz I'm asking for lower bounds for problems. – natema 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 – natema 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
show 3 more comments

2 Answers

up vote 9 down vote

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

share|improve this answer
up vote 1 down vote

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.

share|improve this answer
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
1  
@AJed its not a lower bound on the problem, but its a lower bound on the algorithm. – Realz Slaw Nov 18 '12 at 14:33
And now he edited his question to address "problem" instead of algorithm. – Realz Slaw Nov 18 '12 at 14:34
1  
@RealzSlaw I apologize for being not enough accurate in the text of my question at the beginning. – natema Nov 18 '12 at 17:39
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.