Comment by mlinsey
13 hours ago
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?
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.
I think the bigger issue (for someone hoping for P=NP) is that there's a huge gap between "polynomial" and "exponential." Even if it were the case that all NP problem classes had subexponential decision algorithms, that would not get us close to P=NP.
How much effort has been expended on optimizing those reductions though? I have a harder time believing that one can hang one's belief in P!=NP on that particular hook.
There are so many just barely sub-exponential function shapes between 2^(n / sqrt ln n) {this result} and 2^(log n) {polynomial time}!
The challenge is the initial reduction from an arbitrary problem in NP to the problem you want to prove NP-complete.
In the usual approach, you assume a nondeterministic Turing machine (or equivalent) that solves the problem and a time bound (which can be an arbitrarily large polynomial). You then create a boolean expression that can be satisfied if and only if the Turing machine accepts the original problem instance. Unfortunately all constructions so far have included the time bound as a factor of the size of the expression.
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."
I wonder if there are proofs regarding what neural networks like the transformer can solve. Because fundamentally, Astra is just a bunch of matrix multiplications and a few well defined non-linear functions.
Anyways, most of the times, SAT can be solved quickly, but not always, so getting the answer from Astra in polynomial time doesn't prove much unless you can also prove that it always does, no matter the input.
Iirc, there's a big difference between the computational complexity of what a transformer can solve and what it can solve in practice; what it can solve in practice tends to come from things like singular learning theory (which describes the forms of generalizations that a given ML algorithm can make), but I think (iirc) that transformers can compute a pretty broad class of O(N^2) functions?
For the umpteenth time a transformer is an arbitrary turning machine due to the fact that it has a theoretically limitless tape (the context).
A single transformer step is simply O(1) (for a particular parameter size), but it applied a potentially infinite number of times.
Thus while a single transformer cannot solve any problem, a transformer system applied in the normal way can solve any computable problem.
5 replies →
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.
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.
At certain temperatures water is indeed not wet.
A nontrivial % believe P = NP with some reasonable probability. I wouldn’t say it’s all that settled unlike say RH
Anyone credible? A nontrivial number of people also believe that humans used to ride dinosaurs around like in the Flintstones.
4 replies →
Not the best analogy; water is famously not wet; it makes a surface wet is the common consensus ; wetness is being a property of a surface
No, it is famously a pointless internet debate with no settled answer. There is no scientific definition of what can or can't be wet, saying that wetness only applies to surfaces is just an opinion. It's an entirely linguistic question, and most people would say water is wet. If you want more than descriptivism, the common definition is something like 'containing or being covered with liquid', and I think most people would agree that a mass of water contains water.
I'm beginning to wonder whether P!=NP is undecidable.
Water is not wet. Human lacks water sensor. All the sensors we have a temperature ones so we sense "wet" as a combination of temperature and visual information. Close your eyes, touch water of your skin temperature and you won't sense it. It's not wet.
Stick your head in it and breathe. You'll know.
6 replies →
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).
So, what I heard was "No, and here is a good reason it should be 'yes, some'."
The question was
> does this update your priors significantly in the direction of P=NP?
My answer is no ... and Aaronson's answer would also be no ... clearly he doesn't view a change from 3% to 5% to be significant ... his response downplayed the significance of !ETH in re NP?=P. So apparently you downvoted me for simply stating my own opinion while you completely misunderstood what it was an opinion of.
1 reply →
It might make the third option, that P vs NP cannot be proven true or false, somewhat less likely.
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.
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 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
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.
5 replies →
Why do you "hope" P=NP? It would be a catastrophe
Either P=NP or not. Hoping one way or the other changes nothing. Nor does it change how efficient computing is, nor does it have any effect on cryptography. Discovering a vastly more efficient means of factoring primes--perhaps via quantum computing--would do that. But just learning that P=NP does nothing to further such a discovery. Almost certainly, if P=NP, the exponents and/or constants in a polynomial factoring algorithm would be galactic. (FWIW, Knuth believes that P=NP and that it has no practical consequences.)
Not really. P=NP but the degree of the polynomial is Grahams number doesn't let people into your bank account
it could make lots of compute way more efficient, not sure why it is catastrophe..
1 reply →
Why? Nature doesn't care if people are making financial transactions based on flawed cryptography.
1 reply →