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?
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.
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.
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.
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.
Same idea for that transformer, it needs an infinite context, and it is an infinitely big machine, but with that level of abstraction, it processes a token in O(1).
In practice, there is no such thing as O(1) on arbitrarily sized data, there is no such thing as infinity either, it is just an abstraction.
It’s not the same for transformers, especially not with the theoretical infinite context. It simply doesn’t process tokens in O(1) in your given setup.
In practice, with frontier LLMs, it’s of course more complicated, and also they don’t reveal how they do lookups, but still the theoretical limit applies regardless.
Do you mind elaborating or perhaps providing some reference as to why you think transformers should be similar to a Turing machine on this specific criteria?
So if you use the context not as a tape in itself, but as an io channel to read/write an infinite tape, the context for any given step can remain fixed in size, and so the step itself can be O(1).
The consequence of that is that the original question GuB-42 raised is pretty pointless too. An "inert" transformer effectively has limitations, but as typically used it trivially becomes Turing complete, and so the class of problems it can solve is the exact same class of problems almost any of our other computational devices can solve.
And if you want to point out that this externalises all of what actually matters if we are talking about e.g. intelligence, then yes, it does. But by extension you can trade complexity of the tape for complexity of the machine, and so you can internalise any part of the problem that can be solved with a finite section of tape as a single state transition (trivial proof: For a given machine M with finite state, you can make your machine N execute those steps as a single state transition by having N run M on a state transition.)
To extend that to where I assume they'd want to go in the first place: A transformer wrapped in a loop with access to "just" a "tape head" can "only" be limited from being theoretically able to get all the way to human level intelligence if human brains depend on computations that exceed the Turing computable. But that is no different from any other Turing complete device.
Of course that says nothing of whether it's a practical way of getting there.
Alternatively, you can view the '<unknown>' token that is dynamically driven to the embedding of the output token to be the write head. Either way, the simple truth is that you can train a transformer system (i.e., an iteratively applied transformer) to simulate an arbitrary turing machine.
> In fact it has N read / write heads equal to the size of the context
And what is the asymptotic notation when computation scales linearly with the size of context?
> Either way, the simple truth is that you can train a transformer system
Which still doesn’t mean they have a read/write head or have O(1) complexity for token computation with “infinite context”.
The input to a transformer is a list of embeddings. The output is a list of embeddings of the same length. At the end of the day, you can represent the entirety of the transformer's matrix multiplies and such as a DFA (IEEE 754 float multiplication and addition is a simple DFA, and you're just scaling this up that many times). Thus, you take a list of embeddings (i.e., the tape) and output another, modified, list of embeddings. You have successfully read (ingested) and written (the transformer output) N positions on a tape.
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.
Do you accept
- Moshe Y. Vardi [1]
- Anil Nerode [2]
- Donald Knuth [3]
to be credible? Source for the statements that they consider P=NP to be possible: [4]
And you may include me in the list of credible P=NP believers because treat myself as a credible authority, i.e. when I ask myself whether something is right, I consider myself to be much more credible than some famous scientist. ;-)
(to be very clear: the previous paragraph is rather a clear statement against this kind of "hero worship" with respect to mathematical or scientific problems. One should consider the evidence by oneself instead of believing in P!=NP because lots of computer scientists claim all the time that this is likely true, or consider P=NP now to be possible just because some famous computer scientists consider it to be possible)
---
[1] https://en.wikipedia.org/w/index.php?title=Moshe_Vardi&oldid...
[2] https://en.wikipedia.org/w/index.php?title=Anil_Nerode&oldid...
[3] https://en.wikipedia.org/w/index.php?title=Donald_Knuth&oldi...
[4] https://en.wikipedia.org/w/index.php?title=P_versus_NP_probl...
> to be very clear: the previous paragraph is rather a clear statement against this kind of "hero worship" with respect to mathematical or scientific problems.
No, it's an irrational rejection of the notion of expertise. The experts are not "heroes", they are simply people who have done vastly more study than folks like you or me. e.g., if Magnus Carlsen looks at a complex chess position and says that white is winning, I will trust his judgment far more than my own.
That sounds particularly relevant in how AI-assisted/driven mathematical research is changing the game, where previous assumptions based on human experience/effort are being overturned unexpectedly.
P-vs-NP is no such decision problem. It has a single instance, we just don't know its validity.
I kist thought it was interesting that there are receptors that can detect wetness, just not on the skin. It was a joke pointing that out.
Fuck.
> 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.
Anyway, 3% is very very clearly distinguishable from 0% and so is 5%.
why, because of time.
what does it mean, every key is formed only during the process and no other way! if you understand how the key is formed - you can hack that level, but a new level means a new key.
again: understand, insert - hack
but you can't understand how the key is formed, if you don't see it...
for 50 years people have wanted to find the key, the magical key, I got it, and it's not magical
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.
Would be funny if the most famous problem turns out be an example though
EDIT: I am wrong (it's been a while) but there is nuance.
I said any computer program fails to prove some true statements. In fact, some 'true' statements cannot be proven by any program, as others have said.
But for those statements G, you can prove 'G is true if our system is consistent', just not 'G is true'.
So when we say G is 'true', we are really just asserting the consistency axiom that our computer program is denied.
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.
G is independent of your original system T (cannot be proven true or false).
If you create T+ with added consistency axiom, then G is true and provable.
But G is never true and unprovable in the same system.
It's a lot like is/ought or theology.