Last year I had watched this talk online about problems in $P$ for which an algorithm which runs in some subclass of $P$, say in subquadratic time, would imply $P = NP$, or violate the ETH (exponential time hypothesis). I cannot find this talk and am interested in said problems, for I want to look into quantum algorithms for this group of problems during the semester I'm beginning right now.
Asked
Active
Viewed 253 times
7
-
1
- You might be looking for this talk: https://simons.berkeley.edu/talks/amir-abboud-12-12-2016
– András Salamon Sep 18 '17 at 20:20 -
1If there exists an $O(n^{2-\epsilon})$ algorithm for determining if two DFA's have a non-empty intersection, then SETH is false (and more). Link: https://cstheory.stackexchange.com/questions/29142/deciding-emptiness-of-intersection-of-regular-languages-in-subquadratic-time/29166#29166 – Michael Wehar Sep 19 '17 at 01:48
-
1Lower bounds for problems in $P$ assuming $P \neq NP$ would be pretty surprising. – Huck Bennett Sep 20 '17 at 01:55
1 Answers
8
Virginia Vassilevska Williams lectured at a bootcamp (link to outline) at the Simons Institute, and presents what may be your memory in the introductory video. The whole workshop is worthwhile; the outline and links to videos of all talks can be found here.
She explains (starting at 42:30 in the video) that if there is a $O\left(n^{2-\varepsilon}\right)$ algorithm for some $\varepsilon>0$ for the Orthogonal Vectors problem, then the Strong Exponential Time Hypothesis (SETH) is false. This would not immediately imply $P=NP$, but it would show an $O\left(2^{n-\epsilon}\right)$ algorithm for every $k$-SAT, which would be better than what we have right now; right now we have algorithms which solve $k$-SAT in $2^{n-O\left(\frac{1}{k}\right)}$, so these algorithms tend to $2^{n}$ for large $k$.
The proof is originally by Ryan Williams, and is quite elegant; I do recommend the lecture.
Lieuwe Vinkhuijzen
- 1,969
- 14
- 20