I 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?

▲

jltsiren a minute ago | parent | next [-]

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.

▲

varjag an hour ago | parent | prev | next [-]

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.

	▲	jaaron 14 minutes ago \| parent [-]
		I like this, but the actual finding is a bit different. Trying to keep the water is wet makes this awkward, but I believe it's more like: Everyone agrees that water is wet (P!=NP), but no one can prove it. In the meantime, a whole field of computer science was built on a stronger belief (ETH): that water, at its worst, soaks. Turns out, even at its worst, water only makes things damp. It's still wet. That said, this finding did produce a new measurement of wetness.

▲

novaRom an hour ago | parent | prev [-]

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)

▲

_dain_ 16 minutes ago | parent | next [-]

Why do you "hope" P=NP? It would be a catastrophe

▲

rcpt an hour ago | parent | prev [-]

I don't know if that's a "flaw". It's what Godel Incompleteness guarantees.

Would be funny if the most famous problem turns out be an example though

▲

skew-aberration an hour ago | parent | next [-]

That's not that how that works btw. The incompleteness is a property of the algorithm which does the proofs, not the theorems. If a theorem is true it has a proof and a program which proves it (printf("the proof verbatim")). But no computer program can successfully prove all theorems. The space of potential proofs is too big to search systematically, but you can still get lucky.

	▲	noslenwerdna 7 minutes ago \| parent \| next [-]
		That is also not how it works. The theorem says that there exist some true statements for which there is no proof. This is assuming the axioms are consistent.
	▲	rcpt 18 minutes ago \| parent \| prev [-]
		Godel says that there are statements that are true but have no proof within that system. It's not about algorithms. I'm saying it'd be funny if Riemann were true but not proveable. Though I guess it's actually funnier. If Riemann were false then there would be a counterexample, so it's clearly within existing axioms. So if one can prove that Riemann isn't proveable in our current axioms then it has to be true.

▲

an hour ago | parent | prev [-]

[deleted]