They could have at least compared to them. They barely mention the standard method and leave out an entire class of top tier solutions, the more recent deterministic stratgeies. Shows they did not do their background reading and know the history. More like someone with a tool looking for an interesting application than someone deeply interested in a problem and finding all of the tools which can be used.
They go on to leave out all of the common test problems used in the field. Makes one wonder if the tests were too difficult for neural nets to produce publishable results with, or if they are just ignorant of the research and test problems. They almost state as much in the next paragraph. They don't even .mention how the other algos are capable where they are not.
It's also worth thinking about the environmental cost of the, now three, methods.
I think in this case the attention operation bounds the runtime by the longest possible sequence that can go in at once. Since you have a positional embedding, you can add arbitrarily many more functions without incurring a runtime penalty, although it may begin to interfere with the model's ability to effectively generalize as well, particularly when used with very long sequence lengths (so chains of operations, lists of ints).
Since each operation is mapped to an integer, the maximum number of tokens is bound by the precision of the system.