# What are some problems in $P$ which have lower bounds assuming that $P \neq NP$ or the ETH?

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.

• 2. You might be looking for this talk: simons.berkeley.edu/talks/amir-abboud-12-12-2016 Sep 18 '17 at 20:20
• If 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: cstheory.stackexchange.com/questions/29142/… Sep 19 '17 at 1:48
• Lower bounds for problems in $P$ assuming $P \neq NP$ would be pretty surprising. Sep 20 '17 at 1:55

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$.