This is getting tiresome. I can make the operations as complicated as necessary by comparing all possible permutations of the input string w/ every other permutation & that will not be reducible to standard attention comparisons. The n-gram was a simple example anyone should be able to understand. You can ask your favorite chatbot to compute the complexity for the permutation version.
No worries! I enjoyed it fwiw, appreciate your time :) (The permutation version would be factorial, fwiw, not polynomial. Different beast entirely.)