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 that you have read and understand our privacy policy and code of conduct.