DSPACE (n) = DSPACE (1.5n)?

Do teorema da hierarquia espacial, sabe-se que, se é construtível em espaço, DSPACE ( ) não é igual a DSPACE ( . $f$ $2f(n)$ $f(n))$

Aqui, por DSPACE ( quero dizer a classe de todos os problemas que podem ser resolvidos no espaço por uma máquina de Turing com algum alfabeto fixo. Isso permite considerar o teorema da hierarquia espacial com tanta precisão. $f(n))$ $f(n)$

O argumento padrão fornece a constante multiplicativa : precisamos do espaço para construir um cálculo de alguma máquina de Turing por uma universal. Também precisamos de para resolver um problema com a parada. $2$ $f(n)$ $f(n)$

Pergunta: Is DSPACE ( ) igual DSPACE ( )? $f(n)$ $\frac{3}{2}f(n)$

cc.complexity-theory complexity-classes Alexey Milovanov
fonte

Algum motivo pelo qual você está interessado ? Será que ser igualmente interessante?

\frac{3}{2}

$\frac32$

1 + Ω (1)

$1+\Omega(1)$

Thomas suporta Monica

Por que você acha que o teorema da hierarquia espacial fornece ? Suponho que você defenda que precisamos de espaço para simulação e para contar o número de etapas para evitar loops infinitos. Mas em ambos os casos, precisamos primeiro marcar a ª posição na fita (pode ser feita porque é construtível no espaço) e como você faria a marcação? Seu argumento é bom se você assumir que as máquinas não têm permissão para escrever *, mas, caso contrário, são necessárias outras complicações.

2 f (n)

$2f(n)$

f (n)

$f(n)$

\log_{| Σ |} | Σ |^{f (n)}

$\log_{|\Sigma|} |\Sigma|^{f(n)}$

f (n)

$f(n)$

f

$f$

Domotorp #

@Thomas Na verdade eu quero

1 + o (1)

$1 + o(1)$

Alexey Milovanov

Pode-se provar que DSPACE DSPACE se cresce pelo menos linearmente usando uma variante simples do argumento de preenchimento padrão. Para um idioma , deixe . $(f(\frac 32 n))\ne$ $(f(n))$ $f$ $L$ $L'=\{x0^{|x|/2}\mid x\in L\}$

Afirmação. DSPACE se e somente se DSPACE se . $L\in$ $(f(n))$ $L'\in$ $(f(\frac 23n))$ $f(n)\ge \frac 32n$

(Minha primeira resposta teve várias declarações incorretas, obrigado a Emil por descobrir isso.)

Primeiro, mostrarei como usar a reivindicação para provar a hierarquia. Como cresce pelo menos linearmente, temos DSPACE DSPACE . Pegue um idioma DSPACE DSPACE . Usando a reivindicação, DSPACE DSPACE , onde a última igualdade é pela suposição indireta. Mas então DSPACE DSPACE , onde a última igualdade é novamente pela suposição indireta, dando uma contradição. $f$ $(2f(n))\subset$ $(f(2n))$ $L\in$ $(f(2n))\setminus$ $(f(n))$ $L'\in$ $(f(\frac 43 n))=$ $(f(n))$ $L\in$ $(f(\frac 32 n))=$ $(f(n))$

Prova da reivindicação. Se DSPACE , para provar DSPACE , só precisamos escrever 0 no final da entrada e simular a máquina que aceitou . Como , isso não aumentará o espaço que usamos. (De fato, saber quantos Z 's devem ser escritos não fica claro se é pequeno e não podemos aumentar o tamanho do alfabeto - em vez disso, podemos usar outra fita e escrever sobre tudo o que viria após o final de .) $L'\in$ $(f(\frac 23 n))$ $L\in$ $(f(n))$ $|x|/2$ $x$ $L'$ $f(n)\ge \frac 32 n$ $f$ $x$

A outra direção é simples assim, substituindo os zeros por * 's, se pudermos escrever *' s. (Veja os problemas com isso no meu comentário à pergunta.) Se não temos permissão para escrever estrelas, então modificamos ligeiramente a definição de como . Agora, em vez de escrever estrelas, mantemos a entrada original $L'$ $L'=\{x10^{|x|/2}\mid x\in L\}$ $x10^{|x|/2}$ e trabalhar com isso. Mas sempre que atingimos um 1, seguimos para a direita até atingirmos outro 1 para verificar se foi o final da palavra 1 ou não. Se encontramos outro 1, voltamos ao nosso 1. Se não o encontramos, ainda voltamos, mas saberemos que deve ser tratado como uma estrela - se quisermos escrever sobre ele, também escrevemos um 10 depois dele para ter um novo marcador de fim de palavra atual. (De fato, também há uma pequena captura nessa parte se for pequena - como podemos verificar se a entrada tem o formato ? Sem destruir a entrada, só posso resolver isso usando várias cabeças para pequenas .) $f$ $x10^{|x|/2}$ $f$

domotorp
fonte

Eu não entendo o argumento. De qualquer forma, a construção de preenchimento mostra apenas que, se , então , o que é bastante diferente da reivindicação (lembre-se da localização do ). Da mesma forma, a direção oposta não é clara, como indicado, o que só está claro para mim é que, se , então . Mesmo se eu aceitar a afirmação pelo valor nominal, a prova do resultado principal está errada: fornece apenas .

L \in D S P A C E (f (n))

$L\in\mathrm{DSPACE}(f(n))$

L^{'} \in D S P A C E (f (\frac{2}{3} n))

$L'\in\mathrm{DSPACE}(f(\frac23n))$

\frac{2}{3}

$\frac23$

L^{'} \in D S P A C E (f (\frac{2}{3} n))

$L'\in\mathrm{DSPACE}(f(\frac23n))$

L \in D S P A C E (f (n) + \frac{n}{2})

$L\in\mathrm{DSPACE}(f(n)+\frac n2)$

L \in D S P A C E (2 f (n))

$L\in\mathrm{DSPACE}(2f(n))$

L^{'} \in D S P A C E (\frac{4}{3} f (n) + \frac{n}{3}))

$L'\in\mathrm{DSPACE}(\frac43f(n)+\frac n3))$

Emil Jeřábek 3.0

@Emil Você está certo. Eu tentei consertar, parece melhor?

Domotorp 23/11

Não está totalmente claro para mim qual modelo de máquina você está usando, mas no modelo padrão com uma fita de entrada somente leitura cujo comprimento não conta para o espaço limitado, não vejo como mostrar sem pelo menos uma sobrecarga de espaço . Mas tudo bem, agora acredito que o principal resultado, desde que seja construtível em espaço. Na verdade, ele deve fornecer para qualquer constante iterando o argumento.

L^{'} \in D S P A C E (f (\frac{2}{3} n)) ⟹ L \in D S P A C E (f (n))

$L'\in\mathrm{DSPACE}(f(\frac23n))\implies L\in\mathrm{DSPACE}(f(n))$

O (\log n)

$O(\log n)$

f

$f$

D S P A C E (f (n)) ⊊ D S P A C E ((1 + ϵ) f (n))

$\mathrm{DSPACE}(f(n))\subsetneq\mathrm{DSPACE}((1+\epsilon)f(n))$

ϵ > 0

$\epsilon>0$

Emil Jeřábek 3.0 23/11

@ Emil Não acho que a fita de entrada seja somente leitura - AFAIK, que é assumida apenas se .

f (n) < n

$f(n)<n$

Domotorp

DSPACE (n) = DSPACE (1.5n)?

Respostas: