Рассмотрим следующую проблему:
Для двух строк x, y решите, существует ли строковый гомоморфизм f такой, что f (x) = y.
Легко показать , что эта проблема находится в . Есть ли что-то еще, что мы можем сказать об этой проблеме? Например, это в c o N P или даже в P ?
Эта проблема кажется очень естественной, поэтому я не удивлен, если она была тщательно изучена. Однако я не мог найти эту проблему в литературе.