Gramática sensível ao contexto para SAT?

16

Por um resultado clássico de Kuroda, a classe de complexidade NSPACE [ ]n (também conhecida como NLIN-SPACE) é precisamente a classe CSL de linguagens sensíveis ao contexto . O problema de satisfação SAT está no NSPACE [ ], uma vez que um palpite de tamanho linear para uma solução pode ser verificado com, no máximo, uma quantidade linear de custos indiretos para a contabilidade. Isso significa que o SAT deve ter uma gramática sensível ao contexto (CSG).n

Alguém tentou fornecer um CSG para o SAT?

Sei que muitas perguntas relacionadas a CSLs são indecidíveis (por exemplo, decidir se um determinado CSG gera o idioma vazio). Mesmo com um CSG para o SAT, ainda é preciso superar o obstáculo de que a decisão de se tornar membro do idioma fornecido por um CSG seja completa no PSPACE em geral. Mas pode ser que o problema de associação do CSG que define SAT esteja no NP, devido a alguma estrutura especial do idioma. Reformulando, para abordar o comentário do MCH: Mas pode ser que o problema de associação do CSG que define SAT possa estar no NP devido a alguma estrutura especial da gramática, e não porque já sabemos que ele deve estar em NP.


Esclarecimento:

O foco pretendido aqui é o recurso especial da gramática do SAT, que permite que seja reconhecido por uma máquina NTIME [poly ( )], em vez do NSPACE [ ] DTIME [ ] limite.nn2O(n)

A prova do Teorema 3 no artigo de Landweber de 1963 constrói um CSG a partir de um autômato de limite linear. (Kuroda forneceu o inverso, construindo um autômato de limite linear para qualquer CSG.) No entanto, o procedimento de Landweber parece não produzir uma gramática para SAT que é de forma especial: todos os reconhecedores do NSPACE [ ] são tratados da mesma maneira genérica. Em outras palavras, não está claro por que o SAT CSG deve ter um problema de associação ao NP, em vez de estar completo no PSPACE. Eu esperava uma construção mais explícita que use o NP-Ness do SAT de alguma maneira essencial.n

Talvez uma pergunta melhor, mais precisa, seja:

  1. existe um autômato de limite linear que reconhece SAT,
  2. a partir do qual se pode extrair um CSG,
  3. para que o idioma definido pelo CSG esteja em NP devido a algum recurso da gramática (e não porque já sabemos que está em NP)?

Nas cinco décadas seguintes, certamente alguém tentou fazer isso! Como não consigo encontrar nada publicado nesse sentido, eu estaria interessado em entender por que essa abordagem não funcionou ou como um indicador do trabalho que perdi.

  • Peter S. Landweber, três teoremas sobre gramáticas de estrutura de frase do tipo 1 , Information and Control 6 (2) 131–136, 1963. doi: 10.1016 / S0019-9958 (63) 90169-4
András Salamon
fonte
5
Eu não entendo Você não pode simplesmente seguir a prova e produzir o CSG para SAT? Não é construtivo? Também sobre a última frase, "pode ​​ser que o problema de associação para o CSG que define SAT esteja em NP", está em NP, pois o problema de associação é apenas SAT, que está em NP.
MCH 29/01
11
@MCH: Obrigado pelo seu comentário, espero que a edição esclareça a pergunta.
András Salamon
parece que outra maneira de expressar isso pode ser assim: existem CSLs / CSGs reconhecíveis no tempo NP (em contraste com o PSPACE no caso geral) com base na conversão de SAT. o que há de especial em sua "estrutura" que permite isso? converter SAT em um CSL / CSG pode dar uma "dica", mas não é necessário. dê um critério mais geral. em outras palavras, dado um CSL / CSG arbitrário, existem alguns critérios que indicam que seu reconhecimento está realmente em NP?
vzn

Respostas:

9

Embora não esteja construindo diretamente uma gramática sensível ao contexto para o SAT, o artigo a seguir pode lançar alguma luz.

Rodadas de WC, Complexidade de reconhecimento em linguagens de nível intermediário , Switching and Automata Theory, 1973, 145-158 http://dx.doi.org/10.1109/SWAT.1973.5

O artigo de Rounds fornece um autômato não-determinístico de pilha unidirecional (1-NSA) que reconhece o SAT e, em seguida, mostra o problema de associação do 1-NSA (e seu superconjunto adequado, a Gramática Indexada de Aho) geralmente está em NP. Em outras palavras, o SAT como um CSL / autômato limitado linear é especial no sentido de que usa sua memória apenas como uma pilha.

kinaba
fonte
4
Obrigado, exatamente o que eu estava procurando! Rounds mostra que o SAT é uma linguagem de pilha unidirecional, uma linguagem indexada e uma linguagem de transdutor de árvore, fornecendo três razões teóricas da linguagem diferentes para ser especial.
András Salamon
talvez seja "suficiente", mas não está claro imediatamente se essas condições são necessárias (para que o reconhecimento de CSL / CSG esteja em NP). parece-me que sua pergunta geral pode não ser muito estudada. CSLs / CSGs parecem não ter uma grande quantidade de pesquisas por trás deles.
achou
mais reflexão sobre isso. é um problema geralmente na forma "é o reconhecimento de um idioma na classe Y maior, na verdade na classe X do idioma menor". para Y = CFG e X = RLs (linguagem regular), o problema é indecidível, veja, por exemplo , se este cfg define uma linguagem regular . portanto, Y = CSL e X = NP também parecem indecidíveis em geral.
vzn