I have just learnt about some typical result of fine-grained hardness in 15-455 by Prof Ryan: CNF-SETH implies ${\sf DIAMETER} \notin {\sf TIME}(mn^{1-\epsilon})$. (Here DIAMETER stands for the graph diameter problem).

To prove fine-grained hardness, we construct reductions from $A$ to $B$, then "perturbation" on $A$'s complexity will cause a perturbation on $B$'s. By some fine-grained hardness assumption on $B$, the perturbation on $B$'s complexity is restricted (contradicts the assumption), so such perturbation on $A$'s is disallowed, and kinds of fine-grained hardness result on $A$ is obtained. For example, the proof of ${\sf DIAMETER} \notin {\sf TIME}(mn^{1-\epsilon})$ by CNF-SETH.

In this kind of proof, we can only derive fine-grained hardness from another fine-grained hardness. But where is the initial fine-grained hardness result? i.e. the one not derived from some other fine-grained hardness assumptions. For example, can we prove fine-grained hardness result from "classical hardness" (I'm sorry that I don't know what's the corresponding term), e.g. $\sf P \neq NP$?

The proof technique above seems not work for those classical hardnesses, whose associated complexity classes (e.g. $\sf P$ and $\sf NP$) are very robust by definition. In this case, the small perturbation on $B$ will still fall into the same complexity class, thus won't be prevented by the hardness.

Can fine-grained hardness (e.g. ${\sf DIAMETER} \notin {\sf TIME}(mn^{1-\epsilon})$) be proved directly from classical hardness (e.g., $\sf P \neq NP)$ in some way? What I have learnt is just a brief introduction, and I want to know whether there are some known results (since I failed to find them through Google).



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.