alt Hacker NewsI understand that the Exponential Time Hypothesis being false doesn't necessarily mean P=NP, but for people who are a lot more knowledgeable about complexity theory, does this update your priors significantly in the direction of P=NP?
Replies
I think that it'd be funny if the polynomial time SAT solver was just "send your SAT instance to Astra and have it try to solve it for a few hours."
It might make the third option, that P vs NP cannot be proven true or false, somewhat less likely.
Imagine you're trying to prove that water is wet (P!=NP). You lack a formalism that could make sense at building a proof even though pretty much everyone agrees from empirical evidence that the water is indeed wet. A promising attempt at building one such formalism was just demonstrated by a model to be a dead end.
No. Scott Aaronson said that it changed it from 3% to 5% for him, which is a lot more generous than I would be (but he knows far more about the subject than I do).
For me, this result is significant. It basically adds much more hope P is equal NP (that majority seems being against). I believe one day AI will explain a major flaw in modern mathematics, so a kind of correction in axioms will be suggested to prove Rieman's hypothesis (or a completely new apparatus)
I think it would have to if you're honest with yourself. Any proof of a novel implication of P=NP, such as !ETH, should increase your belief in the two sets' equality. Just as any novel implication of P≠NP should adjust your belief the other way.
My thesis was around showing implications of few different hardness conjectures. So grounded was ETH that I introduced it in a side note as Conjecture 0 after Conjectures 1 and 2. I don't think it's easy to express how substantial of a Bayesian update this is all around.
It's been a long time since I seriously thought about complexity theory, but I'd say no. For similar reasons to why complexity class E is not closed under polynomial-time reductions.
The most important component in the time bound is of the form 2^{n / polylog(n)}, which is subexponential. But if you have reduction from another problem that increases instance size quadratically, the algorithm for the other problem is no longer subexponential. Which means we are still essentially in the same neighborhood as before.
It's a huge result if true, and probably the first major AI result that affects the papers I read. But since the boundary in the hypothesis was kind of arbitrary, breaching it should not significantly change our intuition on complexity classes.