Rozważ następujący problem:
Biorąc pod uwagę dwa ciągi x, y, zdecyduj, czy istnieje homomorfizm ciągu f taki, że f (x) = y.
Łatwo jest pokazać, że problem ten jest w . Czy są inne rzeczy, które możemy powiedzieć o tym problemie? Jest to na przykład w c o N P lub nawet P ?
Ten problem wydaje się bardzo naturalny, więc nie jestem zaskoczony, jeśli został dokładnie zbadany. Jednak nie mogłem znaleźć tego problemu w literaturze.