Złożoność przestrzeni rozpoznawania palindromów Watsona-Cricka

Mam następujący problem algorytmiczny:

Określ przestrzeń Turinga złożoności rozpoznawania ciągów DNA, które są palindromami Watsona-Cricka.

Palindromy Watsona-Cricka to ciągi, których odwróconym dopełnieniem jest ciąg oryginalny. Dopełnieniem jest zdefiniowany litery mądry inspirowany DNA: A jest dopełnieniem T, a C jest dopełnieniem G. prosty przykład dla WC-palindrom jest ACGT.

Wymyśliłem dwa sposoby rozwiązania tego.

Jeden wymaga miejsca.$\mathcal{O}(n)$

• Po zakończeniu pracy urządzenia odczytać dane wejściowe. Taśma wejściowa musi zostać skopiowana na taśmę roboczą w odwrotnej kolejności.
• Maszyna następnie odczyta taśmy wejściowe i robocze z lewej strony i porówna każdy wpis, aby sprawdzić, czy komórka na taśmie roboczej jest komplementem komórki na wejściu. Wymaga to spacji .$\mathcal{O}(n)$

Drugi wymaga miejsca .$\mathcal{O}(\log n)$

• Podczas czytania wejścia. Policz liczbę wpisów na taśmie wejściowej.
• Po zakończeniu odczytu taśmy wejściowej
  • skopiuj dopełnienie litery na taśmę roboczą
  • skopiuj literę L na koniec taśmy roboczej
• (Punkt pętli) Jeśli licznik = 0, wyczyść taśmę roboczą i napisz tak, a następnie zatrzymaj
• Jeśli taśma wejściowa ma wartość L
  • Przesuń głowicę wejściową w lewo o liczbę razy wskazaną przez licznik (wymaga drugiego licznika)
• Jeśli taśma wejściowa ma wartość R
  • Przesuń głowicę wejściową w prawo o liczbę razy wskazaną przez licznik (wymaga drugiego licznika)
• Jeśli komórka przechowująca wartość na taśmie roboczej pasuje do bieżącej komórki na taśmie wejściowej
  • zmniejsz licznik o dwa
  • Przesuń jeden w lewo lub w prawo w zależności od tego, czy R lub L znajdują się odpowiednio na taśmie roboczej
  • skopiuj Uzupełnienie L lub R na arkusz roboczy zamiast aktualnego L lub R.
  • kontynuować pętlę
• Jeśli wartości się nie zgadzają, wyczyść taśmę roboczą i napisz nie, a następnie zatrzymaj

Wynika to z około miejsca do przechowywania obu liczników, aktualnego uzupełnienia oraz wartości L lub R.$2\log n+2$

Mój problem

Pierwszy wymaga zarówno czasu liniowego, jak i przestrzeni. Drugi wymaga czasu i spacji. Dostałem problem z cytatu i wymyśliłem te dwa podejścia, ale nie wiem, z którego wybrać. Muszę tylko nadać przestrzeni złożoność problemu. log$\frac{n^2}{2}$$\log n$

Powód, dla którego jestem zdezorientowany

Powiedziałbym, że druga jest najlepszą opcją, ponieważ jest lepsza pod względem czasu, ale ta odpowiedź pochodzi tylko od mojego szczęścia i wymyślenia algorytmu. Wygląda na to, że jeśli chcę nadać przestrzeni coś złożoności, nie wymagałoby szczęścia w znalezieniu odpowiedniego algorytmu. Czy coś brakuje? Czy powinienem nawet wymyślić rozwiązanie problemu, aby rozwiązać złożoność przestrzeni?

Oświadczenie : Poniższy algorytm nie używa standardowego modelu złożoności sublinearnej przestrzeni (patrz WP: DSPACE ), ponieważ zapisuje na taśmie wejściowej. Ponadto zestawu palindromów (Watson-Crick) nie ma w . Niemniej jednak jest to rozwiązanie na miejscu do wielu praktycznych celów (np. Jeśli każda litera jest literą C).$\mathsf{DSPACE}(\mathcal{O}(1)) = \mathsf{REG}$char

Aby pokazać, że problem ma określoną złożoność przestrzeni, ogólnie trzeba wymyślić algorytm o tej złożoności przestrzeni. Może to wymagać prób i błędów, ale lepszym rozwiązaniem jest dobre zrozumienie problemu, na który patrzysz, oraz duże doświadczenie w zakresie algorytmów i złożoności.

W tym konkretnym przykładzie istnieje trzeci algorytm, który nie wymaga dodatkowej przestrzeni i wymaga złożoności czasowej . Ten algorytm byłby stałą przestrzenią.$O(n^2)$

Wskazówka: po co używać dodatkowej przestrzeni, skoro można wykorzystać przestrzeń zajmowaną przez dane wejściowe?

Wskazówka: przesuwaj suwak w przód i w tył sprawdzając po jednym znaku na raz - użyj stanu maszyny Turinga, aby zapamiętać, który znak sprawdzasz, i usuń znaki, które już sprawdziłeś.

Sposób, w jaki pytanie jest zadawane, powinien wymyślić górną granicę i dolną granicę złożoności przestrzeni.

Pierwsza część jest zwykle wykonywane przez przedstawienie algorytmu dla problemu, ale zmniejszenie do innego dobrze badanego problemu byłoby również praca (i pośrednio wydajność algorytmu, zbyt). Ponieważ nie bierzesz pod uwagę złożonej złożoności (czasu i przestrzeni), tylko przestrzeń ma znaczenie, nawet jeśli czas się wydłuża. Znalazłeś więc górną granicę .$\mathcal{O}(\log n)$

Druga część jest zwykle dużo trudniejsza, ale możesz łatwo pokazać, że stała przestrzeń nie wystarcza, ponieważ dzięki temu Twój język będzie regularny. Używając lematu pompowania z, powiedzmy , gdzie jest założoną liczbą pompowania załatwi sprawę. To wciąż pozostawia dużą lukę między a . l ω ( 1 ) O ( log n $a^lb^{2l}a^l$$l$$\omega(1)$$\mathcal{O}(\log n)$

Znalazłem ćwiczenie (patrz Ćwiczenie 6), które daje pewne wskazówki. Jeśli poprawnie interpretuję ich wskazówkę, spróbuj udowodnić, że istnieje wiele różnych klas równoważności relacji Myhill-Nerode dla każdego rozmiaru wejściowego. Jest to podobne do argumentu, że nie można odróżnić więcej niż ciągów o długości (gdzie to alfabet taśmy, a złożoność przestrzeni). To da ci dolną granicę . n Γ s ( n ) Ω ( log n $c\cdot\Gamma^{s(n)}$$n$$\Gamma$$s(n)$$\Omega(\log n)$

Pamiętaj, że nie musisz przejmować się dopełnianiem liter, ponieważ ta operacja jest banalna, więc wszystko, co działa dla zwykłych palindromów, można zmodyfikować kilkoma dodatkowymi stanami, aby rozwiązać problem.

Jest bardzo prawdopodobne, że klasyczny kompromis czasu i przestrzeni dla palindromów ma również miejsce w twoim przypadku. Ten wynik stwierdza, że ​​maszyna Turinga rozpoznająca palindromy w przestrzeni musi zająć czas , tj. W twoim przypadku pierwszy algorytm ma , a drugi ma . Można również pokazać, że dolna granica przestrzeni to . Nie byłem w stanie znaleźć najlepszej górnej granicy - to znaczy, czy istnieje algorytm wykorzystujący przestrzeń logarytmiczną i czas , czy ogólnie dla jakich wartościΩ ( n 2 / S ) Czas × Spacja = Ω ( n 2 ) . T S = Θ ( n 2 ) T S = Θ ( n 2 log n ) Ω ( log n ) O ( n 2 / log n ) S Ω ( n 2 / S $S$$\Omega(n^2/S)$