La complexité de l'espace de reconnaître palindromes Watson-Crick

Question

J'ai le problème algorithmique suivant:

  

Déterminer l'espace de reconnaître la complexité Turing des chaînes d'ADN qui sont palindromes Watson-Crick.

palindromes Watson-Crick sont des chaînes dont le complément du reverse engineering est la chaîne d'origine. complément est défini inspiré par l'ADN lettre sage,:. A est le complément de T et C est le complément de G. Un exemple simple pour un WC-palindrome est ACGT

Je suis venu avec deux façons de résoudre cela.

Un besoin $ \ mathcal {O} (n) $ espace.

• Une fois la machine fait la lecture de l'entrée. La bande d'entrée doit être copié sur la bande de travail dans l'ordre inverse.
• La machine sera ensuite lire les bandes d'entrée et de travail de la gauche et comparer chaque entrée pour vérifier la cellule dans la bande de travail est le complément de la cellule dans l'entrée. Cela nécessite $ \ mathcal {O} (n) $ espace.

L'autre exige $ \ mathcal {O} (\ log n) $ l'espace.

• Pendant la lecture de l'entrée. Comptez le nombre d'entrées sur la bande d'entrée.
• Lorsque la bande d'entrée se fait lecture
  • copier le complément de la lettre sur la bande de travail
  • copie la lettre L à la fin de la bande de travail
• (point de boucle) Si le compteur = 0, le oui clair de worktape et d'écriture, puis l'arrêt
• Si la bande d'entrée lit L
  • Déplacez la tête d'entrée vers la gauche par le nombre de fois indiqué par le compteur (nécessite un second compteur)
• Si la bande d'entrée lit R
  • Déplacez la tête d'entrée vers la droite par le nombre de fois indiqué par le compteur (nécessite un deuxième compteur)
• Si la cellule qui contient la valeur sur le worktape correspond à la cellule en cours sur la bande d'entrée
  • décrémenter le compteur par deux
  • Déplacer une à gauche ou à droite selon que R ou L est sur la worktape respectivement
  • copier le complément de L ou R à la worktape à la place du courant L ou R
  • continuer la boucle
• Si les valeurs DonT correspondance, désactivez la worktape et écrire non, arrêter

Il sort à environ 2 $ \ log n + 2 espace $ pour stocker les compteurs, l'effectif actuel, et la valeur L ou R.

Ma question

La première exige à la fois du temps et de l'espace linéaire. Le second exige $ \ frac {n ^ 2} {2} $ temps et $ \ log n $ espace. On m'a donné le problème de la citation et est venu avec ces deux approches, mais je ne sais pas lequel pour aller avec. Je dois juste donner la complexité de l'espace du problème.

La raison pour laquelle je suis confus

Je aurais tendance à dire que le second est la meilleure option, car il vaut mieux en termes de temps, mais cette réponse ne vient que de me avoir la chance et à venir avec un algorithme. Il semble que si je veux donner la complexité de l'espace de quelque chose, il ne serait pas compter sur la chance à venir avec l'algorithme de droite. Est-ce que je manque quelque chose? Dois-je être encore à venir avec une solution au problème pour répondre à la complexité de l'espace?

Answer 1

Disclaimer : L'algorithme suivant ne pas utiliser le modèle standard de la complexité de l'espace sous-linéaire (voir WP: DSPACE ), car il écrit sur la bande d'entrée. De plus, l'ensemble de (Watson-Crick) palindromes est pas $ \ {mathsf DSPACE} (\ mathcal {O} (1)) = \ {mathsf REG} $. Néanmoins, il est une solution en place pour de nombreuses raisons pratiques (par exemple, si chaque lettre est un char en C).

Pour montrer qu'un problème a une complexité spatiale spécifique, il faut généralement trouver un algorithme qui a cette complexité de l'espace. Cela peut nécessiter tâtonnement, mais une meilleure approche est d'avoir une bonne compréhension du problème que vous êtes à la recherche et une bonne quantité d'expérience dans les algorithmes et la complexité.

Pour cet exemple particulier, il y a un troisième algorithme qui n'a pas besoin d'espace supplémentaire et nécessite O $ (n ^ 2) $ complexité du temps. Cet algorithme serait un espace constant.

Astuce: pourquoi utiliser plus d'espace, lorsque vous pouvez utiliser l'espace occupé par l'entrée

Astuce: zip arrière-et-vient à travers la chaîne de vérification d'un caractère à la fois - utiliser l'état de la machine de Turing de se rappeler quel personnage vous vérifiez et effacer les caractères que vous avez déjà coché

.

Answer 2

La façon dont la question est posée, vous devriez trouver une limite supérieure et bas lié sur la complexité de l'espace.

La première partie se fait habituellement en présentant un algorithme pour votre problème, mais une réduction de un autre problème bien étudié travailleraient aussi (et indirectement donné un algorithme, aussi). Puisque vous ne considérez pas une complexité combinée (temps et espace) que les questions spatiales, même si le temps augmente. Donc, vous avez trouvé une limite supérieure de $ \ mathcal {O} (\ log n) $.

La seconde partie est généralement beaucoup plus délicat, mais vous pouvez facilement montrer que l'espace constant ne suffit pas, car cela rendrait votre langue régulière. En utilisant le lemme de pompage avec, disons $ a ^ lb ^ {} a ^ 2l l $, où $ l $ est le nombre de pompage supposé fera l'affaire. Cela laisse encore un écart important entre $ \ omega (1) $ et $ \ mathcal {O} (\ log n) $.

J'ai trouvé un exercice (voir exercice 6) qui donne quelques conseils. Si j'interpréter correctement leur indice, essayez de démontrer qu'il existe de nombreuses classes d'équivalence de la relation Myhill-Nerode pour chaque taille d'entrée. Ceci est similaire à l'argument selon lequel vous ne pouvez pas distinguer plus de $ c \ cdot \ Gamma ^ {s (n)} $ strings de $ longueur n $ (où $ \ Gamma $ est votre alphabet de bande et s (n de $) $ la complexité de votre espace). Cela vous donnera une limite inférieure de $ \ Omega (\ log n) $.

---

Notez que vous n'avez pas besoin de se soucier du complément de lettres puisque cette opération est triviale, donc tout ce qui fonctionne pour les palindromes ordinaires peuvent être modifiés avec quelques états pour résoudre votre problème.

Answer 3

Il est très probable que le occupe également une dans votre cas. Ce résultat Etats qu'une machine de Turing reconnaissant palindromes dans l'espace $ S $ doit prendre le temps $ \ Omega (n ^ 2 / S) $, à savoir $$ \ textrm {Temps} \ times \ textrm {Espace} = \ Omega (n ^ 2). $$ Dans votre cas, le premier algorithme a $ TS = \ Theta (n ^ 2) $, et le second a $ TS = \ Theta (n ^ 2 \ log n) $. On peut aussi montrer que la limite inférieure de l'espace est $ \ Omega (\ log n) $. Je ne l'ai pas été en mesure de trouver quelle est la meilleure limite supérieure - qui est, s'il existe un algorithme en utilisant l'espace logarithmique et le temps $ O (n ^ 2 / \ log n) $, ou en général, pour quelles valeurs de $ S $ peut nous obtenir un temps $ \ Omega (n ^ 2 / S) $. À titre d'exercice, vous pouvez essayer de trouver d'autres algorithmes hybrides vos deux algorithmes d'interpolation.