Relação entre ESPAÇO (n) e E

8

Sabe-se se ESPAÇO (n) (a classe de linguagens reconhecida por TMs determinísticas com espaço linear) é um subconjunto apropriado de E (a classe de linguagens reconhecida por TMs determinística no tempo 2 ^ O (n))?

cc.complexity-theory complexity-classes Robin Kothari
fonte

3

é claro que a palavra-chave aqui é 'apropriada', pois a contenção é trivial.

Suresh Venkat

16

Se de fato DSPACE (n) = E, um argumento de preenchimento traduziria isso para PSPACE = EXP. Da mesma forma, se DSPACE (n) E, um argumento de preenchimento traduziria isso para L P. $\neq$ $\neq$

Kristoffer Arnsfelt Hansen
fonte

Não vejo por que DSPACE (n) ≠ E se traduz em L ≠ P. O argumento padding é uma ferramenta para provar condicionalmente que, se algumas classes de complexidade são iguais, outras classes maiores também são iguais. (Veja: en.wikipedia.org/wiki/Padding_argument )

MS Dousti

4

+1 por sucessão! @Sadeq: Isso mesmo. Tome o contrapositivo de sua reivindicação. Você receberá "Se classes maiores não forem iguais, classes menores não serão iguais".

Robin Kothari

@Robin: Você está certo. Eu não vi o :) óbvio

MS Dousti

1

Nota antes de ler

A seguinte prova é falha, como apontado em um comentário abaixo por Robin Kothari. Sou grato a ele por esclarecer o ponto. No entanto, não removi esta resposta, pois acho instrutivo estar ciente de tal falha.

Eu acho que a parte "apropriada" pode ser provada usando teoremas da hierarquia de tempo e espaço. (Veja as seções 7.2 e 7.3 da Complexidade Computacional de Papadimitriou ).

Para uma função construtível no tempo e no espaço , temos: $f(n) \ge n$

$DSPACE(f(n)) \subseteq NSPACE(f(n))$

$\exists k \quad NSPACE(f(n)) \subseteq DTIME(k^{\log n + f(n)})$

$DTIME(f(n)) \subset DTIME(f(n)\log^2 f(n))$

( indica subconjunto apropriado .) $\subset$

Portanto, para a função linear , existe um tal que: $f(n)=n$ $k$

$DSPACE(n) \subseteq DTIME(k^{\log n + n}) \subseteq DTIME(k^{2n}) \subset DTIME((k^{2n})(\log^2 (k^{2n})))$

O lado direito é um subconjunto adequado de E.

MS Dousti
fonte

Isto está errado. No acima, k depende do idioma específico.

Kristoffer Arnsfelt Hansen

Você poderia elaborar sobre qual idioma você está falando? E, de qualquer forma, não basta assumir que existe algum k?

MS Dousti 23/09/10

Tal ak existe para cada idioma no DSPACE (n). Ou seja, se você me der um idioma L no DSPACE (n), eu darei ak para o qual L também está no

. Mas isso não nos diz que existe um k que simplesmente funciona para todos os idiomas no DSPACE (n).

D T I M E (k^{2 n})

$DTIME(k^{2n})$

Robin Kothari

@ Robin: Obrigado Robin. Entendi a falha e editei a resposta para avisar o leitor que ela é falha.

MS Dousti 24/09/10

0

O zoológico da complexidade relata que E não é igual ao PSPACE, citando o artigo Comparando classes de complexidade de Ronald V. Book.

As seguintes frases podem ser facilmente derivadas:

ESPAÇO (n) é um subconjunto apropriado do PSPACE. (1) A
união PSPACE E não está vazia. 2)

Se, em vez de E, tivéssemos EXPTIME, seria fácil deduzir que SPACE (n) é um subconjunto adequado de EXPTIME, devido a (1) e que PSPACE é um subconjunto de EXPTIME.

Para E, a relação entre PSPACE e E não é clara para mim:

1) E está contido no PSPACE?

Caso contrário, segue-se que ESPAÇO (n) é um subconjunto adequado de E. Para verificar isso, é necessário criar um problema que use mais que o espaço linear e menos que o tempo O (2 ⁿ ).

2) O PSPACE está contido em E?

Isso, acredito, é ainda mais difícil de responder do que a pergunta anterior.

chazisop
fonte

1

Você pode explicar o argumento por trás de "Como SPACE (n) é um subconjunto do PSPACE, segue-se que SPACE (n) não é igual a E"?

Robin Kothari

O argumento é válido para EXPTIME, não sei se é válido para E. Consulte a resposta editada para obter mais detalhes.

chazisop

Relação entre ESPAÇO (n) e E

Respostas:

Nota antes de ler