langue Proving dans l'espace complexité

Question

Je voudrais savoir si j'ai la bonne intuition et ma réponse est dirigée dans le bon sens.

Je suis donné une fonction $ F = \ {0, 1 \} ^ * \ rightarrow \ {0, 1 \} ^ * $ qui est calculable dans l'espace $ O (\ log n) $ supposons que pour chaque $ x \ in \ {0, 1 \} ^ * $, $ f $ est longueur conservateurs, $ | f (x) | = | X |. $

Définir $$ = L \ left \ {x \ #Y \ mid \ x, y \ in \ {0, 1 \} ^ *, | x | = | Y |, \ \ texte {et} \ f (x) = f (y) \ right \} $$

Je suppose de prouver que $ L \ dans {\ sf DSPACE} (\ log n) $.

S'il vous plaît me corriger si mon intuition est incorrecte.

Ma solution serait de construire un decider $ M $ qui est une machine de Turing.

$ M $ prend entrées $ x $ et $ y $, exécuter la fonction $ f $ sur l'entrée $ x $ et $ y $ et si les longueurs des deux chaînes sont égales alors accepter, sinon rejeter.

Maintenant, la machine de Turing fonctionne en $ O (\ log n) $ parce que la fonction $ f $ est calculable en $ O (\ log n) + O (\ log n) = O (\ log n) $ et comparer la longueur retournée par la fonction est O $ (1) $ Ainsi, la langue est décidable par une machine de Turing qui est exécuté en $ O (\ log n) $ et prend seulement l'espace $ O (\ log n) $.

Answer 1

Voici une idée approximative comment résoudre ce problème. Vous comparez $ f (x) $ et $ f (y) $ caractère par caractère. Votre bande est divisée en 4 morceaux. La première est pour simuler $ f (x) $ la seconde pour $ f (y) $, alors vous avez deux parties, l'une qui compte dont le caractère de $ x $ vous êtes actuellement computig, et un autre $ O (\ log n) $ zone qui vous aide à naviguer. Maintenant, les regards programm comme celui-ci

1. Déterminez $ | x | $ et $ | y |. $ (! Stocker en binaire) et vérifier s'il y a la même
2. Compute le premier caractère de $ f (x) $ en simulant sur votre machine. Conservez la sortie dans un TM-état. Pause le calcul de $ f (x) $.
3. Marche $ | x |. + 1 étape $ à droite
4. Simuler $ f (y) $ jusqu'à ce que vous obtenez le premier caractère, vérifier si elle coïncide avec le début de $ f (x) $, si aucun rejet, sinon continuer.
5. Marche $ | x | $ pas à gauche.
6. Répétez les étapes 2.-5. jusqu'à ce que vous vérifier $ f (x) = f (y) $ complètement.

Answer 2

Je crains que vous avez mal lu la question. Ce sont les tailles de $ x $ et $ y $ qui doivent être égaux, et non pas celle de $ f (x) $ et $ f (y) $. Bien sûr, dans ce cas, puisque $ f $ est la longueur de conservation, $ | x | = | Y | $ est le même que $ | f (x) | = | F (y) | $. Mais qu'est-ce donc au sujet de la deuxième partie, $ f (x) = f (y) $?

Une autre raison pour que votre algorithme ne fonctionne pas est qu'il utilise l'espace linéaire. Le calcul de la fonction $ f $ prend espace logarithmique, mais la sortie prend un espace linéaire. Donc, si vous stockez $ f (x) $ et $ f (y) $ sur la bande de travail, vous utilisez l'espace $ \ theta (n) $ plutôt que $ O (\ log n) $.