Jen jsem se snažil naznačit, že zatím nikdo nedokázal, že pro NP-úplné úlohy neexistuje polynomiální deterministický algoritmus.
Nezávisle na této teoretické poznámce to je, jak píšete - onen algoritmus pro parsing je v praxi v nejhorším případě exponenciální (ve skutečnosti to jde u přirozených jazyků většinou polynomiálně a dokonce existuje jazyk bez rekurze, ale bavíme se o O(n)).
ČLÁNKY DO MAILU