If a problem has worst-case lower bound Ω(n^2) and there is an algorithm with W(n) ∈ O(n), What can we say about the possibility, importance and order of optimality about this problem and algorithm?


I'll consider decision problems only, for optimisation problems the question could be quantified in plenty of ways.

I assume that you are asking the following: if a language $L \not\in \mathrm{DTime}(n^2)$ and another language $L' \in \mathrm{DTime}(n)$, how close in some sense $L'$ could be to $L$?

One of the more or less natural measures of closeness is the following one. For each $n \in \mathbb{N}$, $\mathbf{P}(L(x) = L'(x)) > 0$ where $x$ is uniformly distributed among $\{0,1\}^n$. Surprisingly, there exists a language $L \in \mathrm{DTime}(n^2)$ such that for any $L' \in \mathrm{DTime}(n)$ there exists infinitely many values of $n$ such that $\mathbf{P}(L(x) = L'(x)) = 0$. One can prove that using diagonalisation in a very similar way to time hierarchy Theorem:

An algorithm $B$ for the language $L$ will act as follows. $B(x)$ will run the algorithm corresponding to the string $|x|$ in binary form for $|x|^{1.5}$ steps (this takes $O(|x|^{1.5} \log |x|)$ time) and answers $0$ if $\langle|x|\rangle$ (the algorithm) did not halted and $1-\langle|x|\rangle(x)$ otherwise. For each algorithm in $\mathrm{DTime}(n)$ there are infinitely many equivalent algorithms and therefore the length of the encoding string of one of them is such that $|x|^{1.5} > cn$ where $c$ is a constant such that $\langle|x|\rangle$ does at most $cn$ steps. Thus $B$ will run $\langle|x|\rangle$ for sufficient number of steps and return the opposite value for any $y \in \{0,1\}^{|x|}$.


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.