On the non-existence of a simple version of the polynomial algorithm for extracting the root from the language

For the usual operation of concatenation of words considered as multiplication, the concatenation of languages is obviously determined, and on the basis of the last operation, the degree of the language and the root of a given degree (if available) is determined. When describing algorithms for constructing a language that is a root of degree M from a given language, so called potential roots are of great importance: these are the words (not the languages) whose considered M-th degree is included in a given language. It is easily to show that all potential roots for a given language are constructed using a polynomial algorithm. This task, apparently, is not simplified when considering words and languages over the 1-letter alphabet, which is done in this paper. So called taboo pair of potential roots is a pair whose word concatenation is not included in the language. In previous publications on the topic of describing algorithms for extracting roots from a language, the hypothesis arose that a polynomial algorithm for extracting a root from a language can be described on the basis of considering the set of taboo pairs only, by iterating over specially described subsets of the set of potential roots. This paper shows, that such an algorithm (called “simple”) is impossible, i.e., if there is a polynomial algorithm for extracting the root from the language, then this algorithm must use some additional information.