О проблеме равенства конечно-порожденных классов экспоненциально-полиномиальных функций

Рассматривается класс $\mathrm{EP}_{\mathbb N}$ экспоненциально-полиномиальных функций, которые можно получить произвольными суперпозициями из констант 0, 1 и арифметических функций сложения, умножения и возведения в степень. Для этого класса решается алгоритмическая проблема равенства двух функций, принимающих конечное число значений. Далее этот класс сужается до класса $\mathrm{PEP}_{\mathbb N}$, в котором функция $x^y$ заменена последовательностью функций $\{p_i^x\}$, где $p_0, p_1,\ldots$ — все простые числа. Для класса $\mathrm{PEP}_{\mathbb N}$ проблема принадлежности функции конечно-порожденному классу эффективно сводится к проблеме равенства двух функций. Последняя проблема эффективно решается для множества всех одноместных функций из $\mathrm{PEP}_{\mathbb N}$.