Jan Martens: Using the Strong Exponential Time Hypothesis (SETH) to show the hardness of PTIME problems.


Event Details


Unconditional lowerbounds on run-time complexity are challenging. For instance, the best known lowerbound for CNF-SAT remains only linear, despite considerable research effort. Nevertheless, we consider NP-hardness a reliable indication that we should not search for a polynomial time algorithms. Having a similar framework indicating the intrinsic difficulty of problems within PTIME, such as linear, quadratic, cubic, etc., would be highly valuable.

In this talk, we will demonstrate how the SETH (Strong Exponential Time Hypothesis), which roughly states that CNF-SAT cannot be solved more efficiently than brute force, provides such hardness-results. Specifically, we demonstrate how SETH implies that deciding the emptiness of the intersection of two deterministic automata is inherently quadratic. This result also directly suggests that solving simulation equivalence for LTSs in subquadratic time is unlikely.

[1] Virginia Vassilevska Williams. “Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk).”  – IPEC 2015

[2] Michael Wehar – “On the complexity of intersection non-emptiness problems” PhD. Thesis 2016, University at Buffalo