Peut

Considérez la langue . $\mathtt{EQUALITY} = \{ a^nb^n \mid n \geq 0 \}$

Il est connu que ne peut être reconnu par aucune machine de Turing à espace sublogarithmique alternatif (ATM) (Szepietowski, 1994) . (Il existe un guichet automatique utilisant un espace sublogarithmique pour les membres mais pas pour tous les non-membres!) $\mathtt{EQUALITY}$

D'autre part, Freivalds (1981) a montré que les machines de Turing probabilistes à espace constant (PTM) à erreurs bornées peuvent reconnaître mais uniquement dans un temps exponentiel attendu ( Greenberg et Weiss, 1986 ). Plus tard, il a été montré qu'aucune erreur bornée -espace PTM ne peut reconnaître une langue non régulière dans le temps attendu polynomial ( Dwork et Stockmeyer, 1990 ). Ma question est $\mathtt{EQUALITY}$ $o(\log\log n)$

si les PTM à espace sublogarithmique poly-temps reconnaissent avec une erreur bornée. $\mathtt{EQUALITY}$

space-bounded polynomial-time Abuzer Yakaryilmaz
la source

Je ne comprends pas pourquoi le titre de la question a été modifié pour supprimer la définition de la langue. Personne n'imaginera que "faire un contrôle d'égalité" signifie "décider de la langue

{a^{n} b^{n} ∣ n \geq 0}

$\{a^nb^n\mid n\geq 0\}$ .

David Richerby

@DavidRicherby: Merci pour votre suggestion et commentaire d'édition. Je préfère juste des titres moins techniques. Sinon, je devrais ajouter non seulement la définition du langage mais aussi les termes "reconnu", "erreur bornée" et "machines de Turing probabilistes".

Abuzer Yakaryilmaz

Le titre doit dire aux gens de quoi traite la question. Il s'agit d'une communauté de chercheurs du TCS et chaque chercheur du TCS sait ce que "reconnu", "erreur bornée" et "machine de Turing probabiliste" signifie. De même, "

{a^{n} b^{n} ∣ n \geq 0}

$\{a^nb^n\mid n\geq 0\}$ " est instantanément compréhensible pour les chercheurs du TCS; "ne vérifie pas l'égalité" ne l'est pas. Si la langauge

{a^{n} b^{n} ∣ n \geq 0}

$\{a^nb^n\mid n\geq 0\}$ avait un nom communément compris, utiliser ce nom serait bien mais, à ma connaissance, ce n'est pas le cas.

David Richerby

Existe-t-il un langage unaire non régulier qui peut être reconnu dans l' espace

(sur une MT déterministe)? S'il n'y en a pas, la même preuve pourrait fonctionner ici.

o (\log n)

$o(\log n)$

domotorp

@domotorp: Oui, il existe des langues non régulières reconnues par

déterministes

-space. (Voir (Szepietowski, 1994) ci-dessus.)

\log \log n

$\log\log n$

Abuzer Yakaryilmaz

J'ai trouvé une réponse à ma propre question. Le résultat a été donné dans la section 5 de Karpinski et Verbeek, 1987 .

Pour toute entrée de longueur , un PTM peut construire un espace avec une forte probabilité (section 4). (Avec une très faible probabilité, la machine peut également construire un espace logarithmique, ce qui peut être considéré comme un "inconvénient" de l'algorithme.) Ensuite, le PTM peut décider si les nombres de ( ) et 's ( ) sont égaux avec une probabilité élevée en utilisant l' espace en temps polynomial. $n$ $\Theta(\log \log n)$ $a$ $n$ $b$ $m$ $O(\log \log n)$

$n \neq m$ $\exists k \leq 4 \log(n+m)$ $n \not\equiv m \mod k$ $k$ $O(\log \log n)$ $O(\log \log n)$ $k$ $n \neq m$ $1 \over 2$

Abuzer Yakaryilmaz
la source

Peut

Réponses: