Pode

Considere o idioma . $\mathtt{EQUALITY} = \{ a^nb^n \mid n \geq 0 \}$

Sabe-se que não pode ser reconhecido por nenhuma máquina de Turing alternada no espaço sublogarítmico (ATM) (Szepietowski, 1994) . (Existe um caixa eletrônico usando espaço sublogarítmico para membros, mas não para todos os não membros!) $\mathtt{EQUALITY}$

Por outro lado, Freivalds (1981) mostrou que as máquinas de Turing probabilísticas de espaço constante de erro delimitado (PTMs) podem reconhecer mas apenas no tempo esperado exponencial ( Greenberg e Weiss, 1986 ). Posteriormente, foi demonstrado que nenhum PTM de espaço limitado de erro delimitado pode reconhecer uma linguagem não regular no tempo esperado polinomial ( Dwork e Stockmeyer, 1990 ). Minha pergunta é $\mathtt{EQUALITY}$ $o(\log\log n)$

se os PTMs de espaço sublogarítmico de tempo polivalente reconhecem com erro delimitado. $\mathtt{EQUALITY}$

space-bounded polynomial-time Abuzer Yakaryilmaz
fonte

Não entendo por que o título da pergunta foi editado para remover a definição do idioma. Ninguém vai imaginar que "fazer verificação da igualdade" significa "decidir o idioma ."

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

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

David Richerby 27/09/13

@ DavidRicherby: Obrigado pela sua sugestão e comentário de edição. Eu apenas prefiro títulos menos técnicos. Caso contrário, devo adicionar não apenas a definição da linguagem, mas também os termos "reconhecido", "erro limitado" e "máquinas de Turing probabilísticas".

Abuzer Yakaryilmaz 28/09

O título deve dizer às pessoas sobre o que é a pergunta. Esta é uma comunidade de pesquisadores do TCS e todo pesquisador do TCS sabe o que significa "reconhecido", "erro limitado" e "máquina de Turing probabilística". Da mesma forma, "

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

$\{a^nb^n\mid n\geq 0\}$ " é instantaneamente compreensível para os pesquisadores da TCS; "fazer verificação de igualdade" não é. Se o idioma

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

$\{a^nb^n\mid n\geq 0\}$ tivesse um nome comumente entendido, seria bom usar esse nome, mas, até onde eu saiba, ele não tem.

David Richerby

Existe uma linguagem unária não regular que possa ser reconhecida no espaço

(em uma TM determinística)? Se não houver, a mesma prova pode funcionar aqui.

o (\log n)

$o(\log n)$

Domotorp #

@domotorp: Sim, existem idiomas não regulares reconhecidos pelas TMs determinísticas do

space. (Veja (Szepietowski, 1994) dado acima.)

\log \log n

$\log\log n$

Abuzer Yakaryilmaz

Eu encontrei uma resposta para minha própria pergunta. O resultado foi dado na Seção 5 de Karpinski e Verbeek, 1987 .

Para qualquer entrada de comprimento , um PTM pode construir com alta probabilidade (Seção 4). (Com uma probabilidade muito pequena, a máquina também pode construir espaço logarítmico, e isso pode ser visto como uma "desvantagem" do algoritmo.) Então, o PTM pode decidir se os números de ( ) e 's ( ) são iguais com alta probabilidade usando o espaço em tempo polinomial. $n$ $\Theta(\log \log n)$ $a$ $n$ $b$ $m$ $O(\log \log n)$

A ideia é a seguinte. Se , então tal que $n \neq m$ $\exists k \leq 4 \log(n+m)$ (Alt e Mehlron, 1976). O PTM pode selecionar umaleatóriousando $n \not\equiv m \mod k$ $k$ $O(\log \log n)$ . também é suficiente para manter um contador e, portanto, tentar mais da metade de todos os 's possíveis . O caso de pode ser detectado com uma probabilidade maior que $O(\log \log n)$ $k$ $n \neq m$ . $1 \over 2$

Abuzer Yakaryilmaz
fonte

Pode

Respostas: