Um idioma no NSPACE (O (n)) e muito provavelmente não no DSPACE (O (n))

10

Na verdade, descobri que o conjunto de idiomas sensíveis ao contexto, ( idiomas aceitos) não são tão amplamente discutidos quanto (idiomas regulares) ou (idiomas sem contexto). E também o problema em aberto não é tão famoso quanto o problema "análogo": " ".CSLR E G C F L D S P A C E ( O ( n ) ) = ? N S P A C E ( O ( n ) ) P = ? N P=NSPACE(O(n))=LBAREGCFLDSPACE(O(n))=?NSPACE(O(n))P=?NP

Bem, existe realmente essa analogia :?

  1. Existe um idioma em que não pode ser provado em (como em idiomas completos)?D S P A C E ( O ( n ) ) N PCSLDSPACE(O(n))NP
  2. Além disso: Existe uma linguagem em que é "completa" no seguinte sentido: se pudermos provar que está em , obtemos essa ?C S L L D S P A C E ( O ( n ) ) D S P A C E ( O ( n ) ) = N S P A C E ( O ( n ) )LCSLLDSPACE(O(n))DSPACE(O(n))=NSPACE(O(n))
  3. (Talvez apenas uma questão de opinião) Os dois problemas estão no mesmo nível de dificuldade?
rl1
fonte
N L P N PL vs. é um problema mais análogo que vs. . NLPNP
Rus9384
Eu acho que você recebeu respostas boas o suficiente; você pode querer aceitar um. Se esses dois respondentes não souberem, a pergunta provavelmente está aberta. Sinta-se à vontade para postar novamente em Teoria da Computação, se você achar útil, mas certifique-se de vincular o link aqui para que as pessoas não percam seu tempo escrevendo as mesmas coisas.
Raphael

Respostas:

8

A versão mais conhecida dessas perguntas é a questão . Se , um argumento de preenchimento (um pouco complicado) mostra que e assim implica a conjectura bem conhecida .L = N L D S P A C E ( n ) = N S P A C E ( n ) D S P A C E ( n ) N S P A C E ( n ) LN LL=?NLL=NLDSPACE(n)=NSPACE(n)DSPACE(n)NSPACE(n)LNL

A conjectura é considerada (por alguns) mais acessível do que a conjectura . Não sei se muitas pessoas têm uma opinião sobre a conjectura .PN P D S P A C E ( n ) N S P A C E ( n )LNLPNPDSPACE(n)NSPACE(n)

A imagem maior aqui é se o teorema de Savitch , que afirma que para razoável , está apertado. Enquanto , acho que a maioria das pessoas acredita que . Por outro lado, não tenho certeza de que as pessoas acreditem que é a explosão ideal; talvez um expoente menor também funcione, pelo menos em alguns casos. Veja, por exemplo, um artigo recente do arXiv , A complexidade de espaço parametrizada da lógica de primeira ordem variável limitada de verificação de modelo , por Yijia Chen, Michael Elberfeld e Moritz Müller.t ( n ) log n N P S P A C E = P S P A C E N S P A C E ( n k ) D S PNSPACE(t(n))DSPACE(t(n)2)t(n)lognNPSPACE=PSPACEt ( n ) 2NSPACE(nk)DSPACE(nk)t(n)2

Yuval Filmus
fonte
Isso ajuda a ver os problemas relacionados. Obrigado por isso.
Rl1 31/07/19
Você disse: "Não tenho certeza de que muitas pessoas tenham uma opinião sobre a conjectura ." Mas a conjectura ainda é objeto de pesquisa, não é? DSPACE(n)NSPACE(n)
Rl1
Se com isso você quer dizer objeto de pesquisa ativa, não tenho certeza. Mas certamente será interessante (para a comunidade) saber a resposta.
Yuval Filmus
Por que o argumento de preenchimento é complicado? Se não significa que o DTM precisa de espaço para simular o NTM? O ( log n )L=NLO(logn)
precisa saber é o seguinte
@ rus9384 Tente realmente executar o argumento para ver a dificuldade ou dê uma olhada no link.
Yuval Filmus
1
  1. Sim, existem idiomas completos da CSL sob reduções DSPACE (O (n)) . Basicamente, ainda é uma variante da acessibilidade direcionada, que pode ser restrita à acessibilidade acíclica, se desejado.
  2. Sim, veja 1.
  3. Você quer dizer, é a pergunta DSPACE (O (n)) = ? NSPACE (O (n)) no mesmo nível de dificuldade da pergunta P = ? NP ? Bem, temos boas razões para acreditar que P é um subconjunto estrito de NP , mas não estou ciente de razões igualmente bem elaboradas para acreditar que DSPACE (O (n)) é um subconjunto estrito de NSPACE (O (n)) . Deixe-me focar na pergunta mais fácil . Passeios aleatórios "não são ruins" para explorar (com relação à acessibilidade) os gráficos não direcionados associados ao SL O ( log n ) O ( log n )L=?NL. A caminhada aleatória análoga trivial óbvia em um gráfico direcionado falhará muito na exploração de um gráfico direcionado (com relação à acessibilidade). Mas talvez haja outras maneiras aleatórias semelhantes de explorar um gráfico direcionado (ou um gráfico acíclico em camadas). Com base no teorema de Savitch, eu até acho que existem essas maneiras, se estivermos dispostos a salvar um conjunto de posições em mudança no gráfico direcionado durante o processo de exploração aleatória. E o desafio seria entender se salvar menos de posições não permitirá uma boa exploração aleatória.O(logn)O(logn)

    Mesmo depois de entendermos se devemos acreditar em , provar que provavelmente será tão impossível quanto provar . Ryan Williams dá uma razão explícita e diz:PN PLNLPNP

    Além disso, não conheço nenhuma razão específica para acreditar que seja "difícil de provar" além da observação de que muitas pessoas tentaram e que nenhuma conseguiu ainda.

    responder ALogTime! = PH difícil de provar (e desconhecido)? Lance Fortnow basicamente levantou a questão e ainda discorda. Minha própria lição foi:

    Isso significa que a declaração "ALogTime! = PH" é exatamente o local onde as dificuldades para provar os resultados da separação começam. Pode-se notar que esta declaração é realmente equivalente a "ALogTime! = NP", pois "ALogTime = NP" implicaria "P = NP = PH".

Thomas Klimpel
fonte
Obrigado! Isso responderia a todas as minhas perguntas, mas eu não entendo sua resposta 1. st-connectivity (alcançabilidade) em gráficos direcionados é um problema completo em ( NL-completo ). Então, você poderia explicar mais a "variante" que você quer dizer (ou fornecer um link)? NL
Rl1 /
@ rl1 A codificação do gráfico direcionado é diferente e, especialmente, seu tamanho é O (exp (n)). Basicamente, o gráfico de transição da máquina de Turing correspondente (com limite de memória fixo).
Thomas Klimpel 02/08/19
Você tem um link para a definição exata da sua variante e para a prova "completenes"?
Rl1
@ rl1 Verifiquei alguns livros introdutórios da teoria da complexidade. O tratamento em Papadimitriou desse tópico é bom e detalhado; o tratamento em Arora / Barak também é bom o suficiente. Menos certeza se o tratamento com Sipser ou Goldreich lhe dará o que você deseja. Papadimitriou também faz sentido, porque este é um livro mais antigo e um tópico mais antigo, e porque o tema da codificação de gráficos de transição por máquinas de Turing adequadamente restritas também ocorre novamente em pesquisas mais recentes de Papadimitriou.
Thomas Klimpel
Papadimitriou (Computational Complexity, 1995) apresenta um exercício que (p. 67) e o teorema de que "REACHABILITY é completo (p. 398). mas isso não responder às minhas perguntas Então, infelizmente, eu não poderia encontrar o resultado que você mencionou na sua resposta em 1. e 2..N LCSL=NSPACE(n)NL
RL1
1

Além das outras respostas, existe uma noção de redutibilidade e integridade para o problema CSL vs. DCSL, ou seja, redutibilidade log-lin, e existem problemas completamente naturais de CSL. Por exemplo, o problema da desigualdade para expressões regulares. Aqui está uma pergunta muito semelhante à sua, juntamente com uma resposta que fornece mais informações e referências: /cstheory/1905/completeness-and-context-sensitive-languages

Hermann Gruber
fonte
-1

SATNTIME(n)DSPACE(n)L=PNPDSPACE(n)DSPACE(n)L=NLDSPACE(n)=NSPACE(n)L=NLL=PNPNSPACE(n)CSL=NSPACE(n)CSLNPCSLcompleteNPCSLNPL=P

L=P

https://hal.archives-ouvertes.fr/hal-01999029

Frank Vega
fonte