2
$\begingroup$

I have seen many problems in graph theory and in other related fields which admit a sublinear (in input size) running time $\mathcal O(n^{1/2})$ algorithm, where $n$ is the input size. I am not sure but to me it seems that fine grained complexity may be one possibility to prove that there is no algorithm with running time $\mathcal O(n^{1/2 - \epsilon})$, where $\epsilon$ is greater than 0. The model of computation is RAM.

Question : How to prove that a problem can't be solved in running time $\mathcal O(n^{1/2 - \epsilon})$?

$\endgroup$
0
2
$\begingroup$

One possibility to get conditional hardness is to give a (fine-grained) reduction from a problem that is known to be hard in some sense. The result will then something along the lines of "if problem X admits an algorithm running in time $O(n^{1/2-\epsilon})$, then problem Y can be solved within some specific time bound". The "specific time bound" should be something we don't know how or believe that can be achieved.

The survey of Williams [1] you refer to contains several examples. As you can see in Figure 1, there are several problems in computational geometry, graph theory, and logic that could be or have been reduced from. Now, for some problems, there is theoretical evidence and belief in the community that the conjectures indeed hold (like ETH). Other ones are less often believed like SETH.

It is an open problem to draw more connections between these problems (see Section 2.6 in [1]), i.e., to find more evidence for hardness other than "here's an isolated problem nobody has been able to find a faster algorithm for decades". For more in this direction, see e.g., this question on CSTheory.


[1] Virginia V. Williams. Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis. IPEC 2015 invited talk.

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