4 ms·

Well, it would depend on how many tokens from the vocabulary are required, in the worst case, to solve NP problems. Think of the tokens as symbols, and of the

by cs702 3y ago

Well, it would depend on how many tokens from the vocabulary are required, in the worst case, to solve NP problems. 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.

nyrikki 3y ago
The Singleton case is NP-complete 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.
- cs702 3y ago
  Thank you. Right now, my puny little brain is searching through what I would describe as "those distant and slightly vague memories" that make up my poor man's knowledge of computational complexity theory. > 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.
  - nyrikki 3y ago
    You don't typically get to the Sigma_2^P level unless are a sadist or forced. 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.
    - cs702 3y ago
      Hmm... 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.
      - nyrikki 3y ago
        My hunch is it will be horses for courses.

by cs702 3y ago

nyrikki 3y ago

The Singleton case is NP-complete 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.

cs702 3y ago
Thank you. Right now, my puny little brain is searching through what I would describe as "those distant and slightly vague memories" that make up my poor man's knowledge of computational complexity theory. > 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.
- nyrikki 3y ago
  You don't typically get to the Sigma_2^P level unless are a sadist or forced. 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.
  - cs702 3y ago
    Hmm... 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.
    - nyrikki 3y ago
      My hunch is it will be horses for courses.