Zdecyduj o istnieniu homomorfizmu strun


11

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 ?NPcoNPP

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.

Odpowiedzi:


16

Jest to omówione w jednym z pierwszych artykułów na temat łańcuchów i złożoności, a mianowicie Dana Angluin, Znalezienie wzorców wspólnych dla zestawu łańcuchów, J. Comput. System Sci. 21 (1980), 46–62. Spójrz na Twierdzenie 3.6. Problem jest NP-zupełny.

Jest również w A. Ehrenfeucht, G. Rozenberg, Znalezienie homomorfizmu między dwoma słowami jest NP-zupełne, Inform. Proces. Łotysz. 9 (1979) 86–88.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.