3
$\begingroup$

Is there a decision problem with a time complexity of Ө(n²)?

In other words, I'm looking for a decision problem for which the best known solution has been proven to have a lower bound of N².

I thought about searching for the biggest number in matrix but the problem is that matrix is an input of O(n²) so the solution is linear.

It doesn't need to be known problem, a hypothetical one would suffice as well.

EDIT I looking for a regular programing problem - not a Turing Machine.

It's could be an arrays, strings, graph etc.

$\endgroup$
  • 1
    $\begingroup$ You may want to specify a computation model, e.g. Turing Machines, Random Access Machines, ... What is quadratic in one model is not necessarily so on others. $\endgroup$ – chi Sep 26 '16 at 8:01
  • 6
    $\begingroup$ "Regular programming problem" is not a model of computation. But it sounds like a random access machine. $\endgroup$ – David Richerby Sep 26 '16 at 8:54
  • 1
    $\begingroup$ What are you willing to assume? For example, there are such lower bounds assuming the Strong Exponential Time Hypothesis (SETH), but not everyone believes it is true. $\endgroup$ – Juho Sep 26 '16 at 11:07
  • 1
    $\begingroup$ @Abdul Yes. In most "practical" cases, you are assuming a RAM model. In Turing Machines, for instance, complexity may differ. E.g. consider the task: given $(i,x_1,\ldots,x_n)$ return $x_i$. In RAM this can be solved in $O(1)$ since array access is constant-time. Using TMs, we need to scan the whole input, so it's $O(n)$. All "reasonable" computational models have complexity which differ by a polynomial factor, at most, so e.g. solving "P vs NP" in a model suffices for all other models. $\endgroup$ – chi Sep 26 '16 at 12:37
  • 2
    $\begingroup$ @Abdul Further, to make things worse, some subfields have different conventions. When dealing with matrices, we usually write $O(n^2)$ even if it is actually linear on the size of the matrix, since we prefer to call $n$ the length of the side. The trivial factorization algorithm for a natural $n$ is $O(n)$ but we regard it as exponential on the number of the digits of $n$, and don't call it "linear-time". One needs to adapt to these conventions and understand their actual meaning -- at the beginning it can be quite confusing. $\endgroup$ – chi Sep 26 '16 at 12:42
6
$\begingroup$

Yes: Checking that a string is a palindrome takes $\Omega(n^2)$ on a single tape Turing machine.

In general the time hierachy theorem implies that there are such problems for most reasonable functions.

For RAM, edit distance can't be solved in $O(n^{2-\epsilon})$ for $\epsilon > 0$ unless the strong exponential time hypothesis is false.

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