<p>Virginia Vassilevska Williams <a href="https://simons.berkeley.edu/talks/computational-complexity-polynomial-time-problems" rel="noreferrer">lectured at a bootcamp</a> (link to outline) at the Simons Institute, and presents what may be your memory in <a href="https://simons.berkeley.edu/talks/virginia-williams-2015-09-01" rel="noreferrer">the introductory video</a>. The whole workshop is worthwhile; the outline and links to videos of all talks can be found <a href="https://simons.berkeley.edu/workshops/complexity2015-boot-camp" rel="noreferrer">here</a>.</p>

<p>She explains (starting at 42:30 in the video) that if there is a $O\left(n^{2-\varepsilon}\right)$ algorithm for some $\varepsilon&gt;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$.</p>

<p>The proof is originally by Ryan Williams, and is quite elegant; I do recommend the lecture.</p>

CC BY-SA 3.0
2017-09-18T21:20:12.443Z
2017-09-18T21:20:12.443Z
Lieuwe Vinkhuijzen
<p>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.</p>

CC BY-SA 3.0
2017-09-18T20:20:54.837Z
2. You might be looking for this talk: https://simons.berkeley.edu/talks/amir-abboud-12-12-2016
András Salamon
CC BY-SA 3.0
2017-09-19T01:48:18.210Z
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: https://cstheory.stackexchange.com/questions/29142/deciding-emptiness-of-intersection-of-regular-languages-in-subquadratic-time/29166#29166
Michael Wehar
CC BY-SA 3.0
2017-09-20T01:55:16.920Z
Lower bounds for problems in $P$ assuming $P \neq NP$ would be pretty surprising.
Huck Bennett
<np-hardness><lower-bounds>
What are some problems in $P$ which have lower bounds assuming that $P \neq NP$ or the ETH?
Samuel Schlesinger
# What are some problems in $P$ which have lower bounds assuming that $P \neq NP$ or the ETH?

(Asked by: username_0 on 2017-09-18)

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.

**Tags:** np-hardness, lower-bounds

> **Comments:**
> **username_1**: 2. You might be looking for this talk: https://simons.berkeley.edu/talks/amir-abboud-12-12-2016  
> **username_2**: 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: https://cstheory.stackexchange.com/questions/29142/deciding-emptiness-of-intersection-of-regular-languages-in-subquadratic-time/29166#29166  
> **username_3**: Lower bounds for problems in $P$ assuming $P \neq NP$ would be pretty surprising.  

---

## 1 answers

### Answer by username_4 on 2017-09-18. Score: 8 | Accepted answer

Virginia Vassilevska Williams [lectured at a bootcamp](https://simons.berkeley.edu/talks/computational-complexity-polynomial-time-problems) (link to outline) at the Simons Institute, and presents what may be your memory in [the introductory video](https://simons.berkeley.edu/talks/virginia-williams-2015-09-01). The whole workshop is worthwhile; the outline and links to videos of all talks can be found [here](https://simons.berkeley.edu/workshops/complexity2015-boot-camp).

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.


---

