I'm looking for examples of problem which has a lower bound of $\Omega(|x|^2$) for input $x$.
The problem needs to have the following properties:
- $\Omega(n^2)$ runtime proof for any algorithm - first priority is to have as simple as possible lower bound argument.
- $O(n^2)$ algorithm, if possible, simple one as well.
- Output size of $O(n)$ (or smaller). Obviously any problem which requires $\Omega(n^2)$ lengthed output required at least similar run time, but that's not what I'm looking for. Notice that any decision problem fits here.
- (if possible) a "natural" problem. Without a formal definition, a problem any CS graduate would recognize is preferable.
I was recently asked about such problem but couldn't come up with a simple one. The first problem that came to mind was $3SUM$, which was conjuctured to be a $\Omega(n^2)$ runtime problem. This was not simple enough and furthermore, the conjucture was recently proven false :o.
Going to an extremely unnatural problem, I believe that the problem that gets as an input a deterministic TM and input $\langle M \rangle,x$, and outputs the position of the tape head after $(|M|+|x|)^2$ steps when it's running on $x$ probably answers the question.
If you absolutely need to, lets agree that we're using the single-tape TM model, although I prefer problems whose runtime is independent on the exact model (as long as it's a reasonable one).
So, can we find a simple (to prove), natural (well known) problem whose runtime is $\Theta(n^2)$?