What is the difference between saying there is no ϵ>0 such that a problem can be solved in $O(n^{2-\epsilon})$ time and $n^{2-o(1)}$ or $\Omega(n^2)$?

Question

I have seen the formulations

there is no ϵ>0 such that a problem can be solved in $O(n^{2-\epsilon})$ time

a problem requires time $n^{2-o(1)}$

a problem requires time $\Omega(n^2)$

being used in the context of lower bounds but I am not sure as to whether there are relevant differences between these notations or if they are simply equivalent. Intuitively, it seems to me like at least the first and third one are while the second one excludes running times like $n^3$ that are included in the others. However, I have also encountered situations where the second one has been used in a similar way to the first one (i.e. the definitions of the Orthogonal Vectors Hypothesis here, p. 6 and here, p. 6) which suggests to me that they are also equivalent. So how do these notations relate to each other?

Answer 1

It is conjectured that 3SUM cannot be solved in time $O(n^{2-\epsilon})$ for any $\epsilon > 0$; equivalently, it requires time $n^{2-o(1)}$. This is not the same as the stronger conjecture that 3SUM requires time $\Omega(n^2)$. Indeed, the latter conjecture (which was the original form of the 3SUM conjecture) is false: Grønlund and Pettie came up with an $O(n^2/(\log n/\log\log n)^{3/2})$ algorithm (there were improvements since).

The statement "problem X requires time $n^{2-o(1)}$" states that there exists a function $f(n) = o(1)$ such that any algorithm for X runs in time at least $n^{2-f(n)}$. In particular, there is no $O(n^{2-\epsilon})$ algorithm, for any $\epsilon > 0$. The converse should also hold, I believe – could be a fun exercise to show.

Answer 2

1. If Your first statement

there is no $\varepsilon>0$ such that a problem can be solved in $O(n^{2−\varepsilon})$ time

we understand as negation of

$\exists\varepsilon>0,f \in O(n^{2−\varepsilon})$

Then it will be $\forall\varepsilon>0,f \notin O(n^{2−\varepsilon})$ which is set $$A=\left\lbrace f:\forall\varepsilon>0, \forall C>0,\forall N\in \mathbb{N}, \exists n>N, f(n) >C n^{2−\varepsilon}\right\rbrace$$ The set from $3$-d statement, $\Omega(n^2)$, as we know, is: $$B=\Omega(n^2)=\left\lbrace f:\exists C>0, \exists N\in \mathbb{N}, \forall n>N, f(n) \geqslant Cn^2 \right\rbrace$$ Now if we consider example $$\phi(n)=\begin{cases} 0, & n=2k-1, k\in \mathbb{N} \\ n^3, & n=2k, k\in \mathbb{N} \end{cases}$$ then $\phi\in A$, but $\phi \notin B$.

2. For your second statement if set $C=n^{2-o(1)}$ can be defined as $$C=\left\lbrace f: \exists \varepsilon(n), \lim\limits_{n \to \infty} \varepsilon(n)=0, \exists N\in \mathbb{N}, \forall n>N, f(n)= n^{2-\varepsilon(n)}\right\rbrace $$ then again $\phi \notin C$.

So for equivalence there is need some additional restrictions, for example monotonicity, which forbids examples like brought above or we need some other understandings for sets $A,C$.

Answer 3

Beginner myself, but here is my attempt(in Layman terms).

1 ) there is no $ϵ>0$ such that a problem can be solved in $O(n^{2−ϵ})$ time

This means that the problem cannot have a worst solution with an order of growth of at most $cn^k$ where $k\in [0,2)$ and $c$ is some +ve constant.

3 ) a problem requires time $Ω(n^2)$

This means that the best solutions to the problem have an order of growth of at least $cn^2$, $c$ being some +ve constant.