Power of Double - Espace logarithmiques

Question

J'essaie de résoudre l'exercice « sur la puissance double - espace logarithmique » du grand livre complexité par Oded Goldreich. L'objectif est de montrer que l'ensemble donné $ S = \ left \ {w_k \ mid k \ in \ mathbb {N} \ right \} $, où $ w_k $ - concaténation de tous -bit $ k $ de longues chaînes séparées par * 's n'est pas régulier et pourtant il est décidable dans l'espace double logarithmique. L'exercice contient des lignes directrices, et je voudrais jeter la lumière sur quelques phrases de lignes directrices afin de résoudre l'exercice.

Dans les lignes directrices qu'il est mentionné que

nous pouvons profiter de la * 's (en $ w_i $), $ i $ e itération peut être mis en œuvre dans l'espace $ O (\ log i) $

Le $ i $ e itération vérifie si $ x = w_i $, ce qui est vraiment peut être décidé en $ O (\ log i) $ l'espace, où $ \ LOGuer $ peut être utilisé pour noter la position $ i $ longue chaîne, mais la position de $ x $ peut être inclus dans $ O (\ log i) $ ou non?

En outre, sur $ entrée x \ S Notin $, nous nous arrêtons et au plus après rejet $ \ Log | x |. $ Itérations

Cela signifie seulement $ \ log | x | $ $ w $ 's de l'ensemble S sera comparé à $ x $. Pourquoi est-il réellement ainsi?

En fait, il est un peu plus simple à gérer l'ensemble connexe $ \ Left \ {W_1 ** w_2 ** .. ** w_k \ right \} $

Pourquoi est-il en fait, et je l'appellerais défini, il est une chaîne plutôt concaténé.

Answer 1

Eh bien, l'ensemble $ \ left \ {W_1 ** w_2 ** .. ** w_k \ right \} $ ne contient qu'un seul élément, mais est néanmoins un ensemble. Et TM ne peut accepter que des langues, qui sont des ensembles de mots.

Pourquoi est-il un peu plus facile? Hmm, je dirais, il est plus facile puisque vous pouvez simplifier l'algorithme légèrement . Vous avez un compteur pour $ k $, puis de vérifier, que ce soit dans la chaîne $ \ cdots * x * y * \ cdots $, vous avez un texte $ \ {bin} (y) = \ texte {bin} (x) + 1 $ sur chaque position. Vous ne devez pas se soucier de détecter le droit $ k $ de. À part cela, la suoer-chaîne est plus longue, ce qui vous donne plus d'espace. Mais cet effet disparaît dans le grand-O.