from the article, to me it seems pretty clear that the message is "finding the complexity for the general case is impossible" (ie for certain, short, strings we can definitely figure it out)