There's not really that much assumption. Given the fact that good and simple linear time algorithms exist for decades it's very unlikely that they use some ridi

There's not really that much assumption. Given the fact that good and simple linear time algorithms exist for decades it's very unlikely that they use some ridiculous permutation enumeration algorithm. Even a Microsoft Research project has a fairly complex reductions implementation of a POS tagger that is blazingly fast and production ready (learning to search interface). [1] [1]: https://github.com/JohnLangford/vowpal_wabbit/wiki https://github.com/JohnLangford/vowpal_wabbit/wiki