Computational Complexity - Research Seminar
Cornelius Brand: The nondeterministic strong exponential time hypothesis
March 3, 2017, 4 p.m.
E 1 3, Room 107
Carmosino et al. (ITCS 2016) introduced the nondeterminsitic strong exponential time hypothesis (NSETH). It states that verifying unsatisfiability proofs of k-CNF-formulas on n variables requires time (2-o(1))^n.
In this talk, I give an overview over their results. They give the first method to show conditional non-reducibility results: Assuming NSETH, the current multitude of hypotheses on the optimal running times of algorithms for some central polynomial-time solvable problems (all-pairs-shortest-paths, 3-sum, orthogonal vectors) cannot be replaced by having only SETH as a single hypothesis.
Interestingly, they only consider problems in P for non-reducibility. They do not give results on hard problems that seem to require exponential time, but have no known reduction from k-CNF-SAT, such as k-Set-Cover, which might be worth discussing.