Статья больше практичная чем хорошая. Нет оценки числа возможных сверток, при этом стала бы очень ярко видна вся убогость описанных методов. А так плохо считающие студенты могут подумать что это очень серьезно, там изложены Открытия-в-ИИ и все такое.
Кому тема интересна пусть сначала посчитают средний размер функции, сравнивающей документы. Желание искать красивую формулу в одну строчку сразу пропадет.
Теоретической ценности статья не представляет. Только рассмотрено что на практике можно сделать. Что могут сделать не использующие компьютеров программисты (не интресующиеся ИИ) на очень ограниченных компьютерах.

NPC не самый плохой класс сложности. Вот новая картинка http://www.csin.ru/blog/2006-08-28-complexity-zoo/
Сложноструктурированость тоже не основная проблема. В начале текста может определяться язык, а сам основной текст уже на нем. Тут проблема не в структуре, а именно в языке. Структура в тексте может быть расписана на всех известных языках, но компьютер этого не поймет и будет искать что-то свое.