19
$\begingroup$

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:

  1. $\Omega(n^2)$ runtime proof for any algorithm - first priority is to have as simple as possible lower bound argument.
  2. $O(n^2)$ algorithm, if possible, simple one as well.
  3. 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.
  4. (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)$?

$\endgroup$
  • $\begingroup$ I think "Given natural numbers $x$, $y$, compute $x+y$" qualifies. Also, note this question. $\endgroup$ – Raphael Sep 26 '14 at 13:07
  • 2
    $\begingroup$ The only way we know how to prove superlinear lower bounds on multitape Turing machines is through diagonalization. For single-tape Turing machines, you can get a bit better using crossing sequences, but not as far as $n^2$ unless perhaps you restrict the space. $\endgroup$ – Yuval Filmus Sep 26 '14 at 13:34
  • 2
    $\begingroup$ See here for another related question; input reversal seems to be a good candidate. $\endgroup$ – Raphael Sep 26 '14 at 13:36
  • $\begingroup$ I don't think you can do it with a decision problem, because the best found lower bound for NP is O(n). $\endgroup$ – Albert Hendriks Mar 4 '15 at 14:38
  • $\begingroup$ Thanks for your comment @AlbertHendriks. Can you please share a reference to a source/survey claiming that the best known lower bound for any problem in NP is $\Omega(n)$? $\endgroup$ – R B Mar 4 '15 at 16:32
7
$\begingroup$

Finding an envy-free cake-cutting requires $\Omega(n^2)$ queries. However, this does not directly answer your question as the computational model is different than a Turing machine.

By the way, currently the quickest known algorithm for this problem requires $n^{n^{n^{n^{n^{n}}}}}$ queries, so there is a huge gap from the lower bound - probably one of the largest gaps in computer science.

$\endgroup$
1
$\begingroup$

As in the link provided by Raphael, Peter shows that Input Reversal requires $\Theta(n^2)$ time on vanilla single-tape TMs. For a decision problem, the language $$L = \{x0^{|x|}x \mid x \in \{0,1\}^\ast \}$$ also provably needs $\Theta(n^2)$ time to compute. To see this, use Peter's communication complexity argument , along with a classical result that $EQ_n$ needs $\Theta(n)$ bits of communication, to show the quadratic lower bound of $L$. The similar approach works for a more natural one $L = \{xx \mid x \in \{0,1\}^\ast \}$.

By the way, it is worth mentioning that the "crossing sequence method" mentioned by Yuval is (to my best knowledge) mathematically equivalent (or, maybe, inforior) to the communication complexity one.


For another candidate that does not directly answer your question, Ryan Williams proved that $\mathsf{SAT}$ cannot be decided in $O(n^{2 \cos(\pi/7)})$ time and simultaneously $n^{o(1)}$ space on RAMs. While the constant $2 \cos(\pi/7) \approx 1.8$ seems quite magical, the initial idea that comes from Fortnow, is ingenious but not so involved. Refer to page 101 in the textbook of Barak and Arora for an exposition of the idea.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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