In the general case that would be the same as hierarchy collapse of PH, which would prove P=NP
If you consider NP-complete as the intersection of NP, which is a decision problem, and NP-hard which a decider function isn't possible; look at the success of heuristics between those two sets.
Existential quantifiers on the second order terms in NP is the same thing.
Over Parameterization can be thought as less lossy compression and attention can be thought of as improved retrieval or as additional expressiveness by not missing out on as many outputs using binary output.
You can consider how LLMs tend to append, resulting in telescope reduction as one of those approximation reductions.
But this is due to the combinatorial optimization, which is far more difficult.
Another way to think about it is that PH is equal to the set of boolean queries on a concurent random acess machine using exponentially many processors and constant time.
If your datasets have the Markovian property and are close to ergotic there are options, but you probably wouldn't need to resort to attention and over parameterization in that case.
The word sense disambiguation problem is probably another lens. That is harder yet but may be a way to think about what I am trying to explain.
Think of the tokens as symbols, and of the vocabulary as a finite alphabet of symbols, in a formal system.
In other words, no, it would NOT necessarily prove P = NP.
If you consider NP second-order existential logic, meaning that given x, you will get a y, While there may be many true values that aren't y, it will help
Attention, which requires feed forward networks, which approximate a DAG, you can think of attention as run time reweighing to change what y value is returned.
PH is a query expressible in second-order logic, which would allow for 'for any' at the second level.
The reduction in the general case to just logarithmic time: O(n log n), would cause issue, there will not be any movement from quadratic time to linear time without massive new discoveries.
It is inherent from the restrictions of ANNs having binary output.
Considering FP and FNP vs P and NP may help as they make that property clearer than the concept of second-order existential logic does in some contexts.
> Attention, which requires feed forward networks, which approximate a DAG, you can think of attention as run time reweighing to change what y value is returned.
Isn't that's true for linear RNN mechanisms too? Note that linear RNNs like RWKV and Mamba are linear in the number of tokens in the sequence, but not in the number of features per token.
Attention works differently in RNNs, and it may be able to find different tractable forms, and may solve different problems, but increasing generalization is a reduction of compression in the general case.
A many to one reduction to a recursively enumerable set gets you to finite time, a reduction to NP gets you to quadratic time.
Obviously those are upper limits and specific instances or classes of instances may do better. P being inside NP is a good example.
All ANNs are binary output, which helps with that. SNN or spikey neutral networks, which better model cortical neurons and have continuous output have problems with being un-computable without much complexity as an example.
That can be viewed as the problems with computable numbers in place of the reals. But there are lots of interesting and practical things to solve. It is just those solutions will be more domain specific IMHO.
You're right: It's quite possible that the new crop of linear RNNs may not be able to solve the same problems as Transformers.
It could also be that we will have to increase the depth of these linear RNNs (possibly even dynamically) to enable them to perform comparably well on all problems. Right now it's hard to tell for sure. I don't know.
What I do know is that recently proposed linear RNNs are performing comparably to Transformers at similar model sizes, but have not yet been evaluated at state-of-the-art scales.
Generally though, I don't think that's quite the same. Collapsing all O(N^2) problems down to O(N) would collapse the hierarchy and prove P=NP, but it's blatantly impossible and would prove a lot of falsehoods too.
PH, or the polynomial hierarchy is the collapse I was talking about, but note I was talking about global and not individual or families of instances.
Schaefer's Dichotomy Theorem shows that HORNSAT is solvable, given those constraints.
I found this paper useful as it reframes it as topology which is helpful to build it intuitions, at least me.
https://arxiv.org/abs/2307.03446
Of the proposed linear self attention like solutions I have seen, they tend to approach it more from what can be reduced the clustering problem.
A lens for that is FTA vs FMEA, being thought of as top down vs bottom up.
Top down is cheaper but may miss things, bottom up doesn't miss things but can result in combinatorial explosion.
This paper covers some optimization problems that are NP-hard to approximate to within a given approximation ratio.
Being able to do so would show P=NP
https://dl.acm.org/doi/pdf/10.1145/321958.321975
But that is under the assumption that increasing the self attention window was to improve accuracy, not to trade accuracy for efficiency.
While this paper is about casual inference and not PAC learning, it is the reason most 'causal AI' is just stocastic search and event trees.