Existe uma restrição natural da lógica do VO que captura P ou NP?

12

O papel

  • Lauri Hella e José María Turull-Torres, Consultas de computação com lógicas de ordem superior , TCS 355 197-214, 2006. doi: 10.1016 / j.tcs.2006.01.009

propõe lógica VO, lógica de ordem variável. Isso permite a quantificação de pedidos sobre as variáveis. O VO é bastante poderoso e pode expressar algumas consultas não computáveis. (Como apontado por Arthur Milchior abaixo, ele realmente captura toda a hierarquia analítica .) Os autores mostram que o fragmento de VO obtido por permitir apenas quantificação universal limitada sobre as variáveis ​​de ordem expressa exatamente todas as consultas ce. O VO permite que as variáveis ​​de ordem ultrapassem os números naturais, portanto, limitar as variáveis ​​de ordem é claramente uma condição natural a ser imposta.

Existe um (bom) fragmento de VO que captura P ou NP?

Como analogia, na lógica clássica de primeira ordem, a quantificação de conjuntos de objetos fornece uma lógica mais poderosa chamada lógica de segunda ordem ou SO. O SO captura toda a hierarquia polinomial ; isso geralmente é escrito como PH = SO. Existem formas restritas de SO que capturam importantes classes de complexidade: NP = SO, P = SO-Horn e NL = SO-Krom. Estes são obtidos impondo restrições à sintaxe das fórmulas permitidas.

Portanto, existem maneiras simples de restringir o SO para obter classes interessantes. Gostaria de saber se existem restrições diretas semelhantes do VO que são aproximadamente o nível certo de expressividade para P ou NP. Se tais restrições não forem conhecidas, eu estaria interessado em sugestões de possíveis candidatos ou em alguns argumentos sobre por que é improvável que essas restrições existam.

Eu verifiquei os (poucos) artigos que citam este e verifiquei as frases óbvias no Google e no Scholar, mas não encontrei nada obviamente relevante. A maioria dos artigos que lidam com lógicas mais poderosas que a de primeira ordem não parece lidar com restrições para derrubar o poder no campo das computações "razoáveis", mas parece satisfeita em habitar o universo das classes aritméticas e analíticas. Eu ficaria feliz com um ponteiro ou uma frase não óbvia para pesquisar; isso pode ser bem conhecido por alguém que trabalha com lógicas de ordem superior.

András Salamon
fonte
5
Embora as abreviações sejam famosas entre a comunidade de CS, eu gostaria de expandi-las para "o resto de nós": PH (Hierarquia de tempo polinomial), SO (lógica de segunda ordem) e VO (lógica de ordem variável).
MS Dousti 3/10/10
1
Na verdade, eu nunca ouvi falar do VO antes disso, então obrigado pelo esclarecimento.
Suresh Venkat
@ Suresh: Sim, eu esqueci de dizer que o VO não é bem conhecido. De qualquer forma, você é bem-vindo!
MS Dousti 03/10/10
Há uma boa ilustração de várias lógicas e classes de complexidade aqui: cs.umass.edu/~immerman/descriptive_complexity.html , embora não mencione o VO.
MS Dousti 3/10/10
Talvez eu não tenha sido claro: o VO foi definido há menos de uma década e não é bem conhecido. Estou interessado porque é uma maneira de estender a lógica de primeira ordem para torná-la mais poderosa, sem usar operadores de ponto fixo.
András Salamon

Respostas:

3

Nota: Isso realmente não está respondendo à pergunta, são apenas alguns comentários postados como resposta. :)

Observe que no VO, definimos conjuntos sobre o conjunto de números naturais (semelhante aos conjuntos definidos na teoria da recursão), onde, como no cenário descritivo da complexidade (SO, -SO, SO-Horn), estamos falando de estruturas finitas. Uma fórmula SO no cenário anterior não fornecerá mas toda a hierarquia analítica, como Arthur Milchior escreveu em sua resposta. IMHO, uma comparação melhor seria com teorias aritméticas limitadas. Eu não acho que você possa obter abaixo dos conjuntos ce, a menos que vincule todos os quantificadores a domínios finitos, para obter ou o tamanho dos domínios deve ser muito pequeno.P H P N PPHPNP

a presença de um quantificador ilimitado é suficiente para capturar conjuntos de ce?

O problema é que você provavelmente quer que a linguagem fique sem símbolos extras como igualdade, adição, multiplicação (certo?), Se os tivéssemos pelo teorema do MRDP, fórmulas diofantinas (quantificadores existenciais de primeira ordem na frente de uma igualdade de dois polinômios) capturaria conjuntos de ce. Se não estamos permitindo esses símbolos no idioma, o problema é mais complicado, pode-se usar quantificadores de ordem superior para defini-los, mas isso aumentaria a complexidade do quantificador. Portanto, se eu quiser dar uma resposta curta à sua pergunta sobre um único quantificador, não sei.

Se pudermos expressar relações na linguagem, um único quantificador existencial ilimitado seria suficiente para capturar conjuntos de ce, o motivo é que pode verificar se uma sequência é o cálculo de uma TM na entrada . Fórmulas de primeira ordem delimitadas por polinômios na presença de igualdade, adição e multiplicação capturam PH, portanto, se as tivermos no idioma, a resposta é positiva, mas como eu disse, você provavelmente está procurando um idioma sem esses símbolos. A C 0 c e xAC0AC0cex

Alguns comentários adicionais:

Suponha que temos uma restrição do VO que pode expressar pelo menos . Então, um único quantificador existencial ilimitado do tipo de número na frente dessas fórmulas restritas fornecerá todos os conjuntos de ce.AC0

Kaveh
fonte
4

Para informação, o VO é realmente mais poderoso do que você declara; contém toda a hierarquia analítica (portanto, também toda a hierarquia aritmética). O resultado não é publicado, nem enviado a nenhum lugar, mas você pode encontrá-lo em minha página, www.milchior.fr/ho.pdf, seção 7, página 47.

Nele, mostro como o VO permite expressar adição e multiplicação na variável de ordem; pode haver alguma idéia neste artigo que possa ajudá-lo. Em particular, dei uma definição equivalente (eu provo que é equivalente) e acho que é mais fácil de usar. (Eu queria evitar o fato de que, na definição de VO é falso, enquanto é verdadeira, o que significa que o foi mudado após foi quantificada, pelo que é inútil adicionar " " quando um quantifica .i X ii Y i ( X i = Y i ) i X i XiXijYj(Xi=Yj)iXiiYi(Xi=Yi)iXiX

Uma restrição direta seria proibir a quantificação da mesma variável duas vezes. Tenho certeza de que a restrição é a classe ELEMENTARY. A idéia é que, para toda fórmula com uma variável de ordem livre , haveria um número tal que, para todo o valor de não mudaria; portanto, se pudermos encontrar esse (que provavelmente é uma função elementar do tamanho do universo), poderemos evitar realmente verificar todos os possíveis quando quisermos o valor de mas restringir para .i k i > k φ ( i ) k φ ( i ) i φ ( i ) i < k φ ( i )ϕ(i)iki>kϕ(i)kϕ(i)iϕ(i)i<kϕ(i)

Senão, você certamente pode restringir o VO restringindo a ordem máxima aceita; mas você obtém uma linguagem de "ordem superior" (HO) e provavelmente não é isso que você deseja.

Arthur MILCHIOR
fonte
Obrigado pela discussão, examinarei sua reformulação. Você tem alguma sugestão de algumas maneiras de restringir a lógica para que ela não seja tão poderosa - algo como exigir que a parte não quantificada da fórmula esteja na CNF com cláusulas de Horn provavelmente seja útil, como acontece com os quantificadores clássicos?
András Salamon
Para ser mais preciso, quero dizer uma restrição sintática ao longo das linhas do SNP, em que os quantificadores de SO são aplicados a uma fórmula FO de forma específica (para SNP, apenas com quantificadores universais de FO) e, em seguida, restrições adicionais são aplicadas, como o Fórmula FO dentro dos quantificadores FO sendo Horn ou Krom. O último parágrafo da sua Seção 5.3 fala sobre isso, mas não entendo o seu comentário de que a abordagem é problemática.
András Salamon
Sugiro que você leia a seção 5.3, página 34 do meu artigo, sobre o problema que encontrei na Horn e Krom na lógica de alta ordem. Você encontrará o mesmo problema na Ordem Variável (que é claramente um superconjunto da Ordem Alta)
Arthur MILCHIOR
2

Para responder ao seu comentário, acho que devo fazer outra resposta, falando apenas em Krom e Horn (talvez eu deva fazer uma pergunta sobre isso ao CSTheory)

Sugiro que você leia a seção 5.3, página 34 do meu artigo, sobre o problema que encontrei na Horn e Krom na lógica de alta ordem. Você encontrará o mesmo problema em Ordem variável (que é claramente um superconjunto de Ordem alta).

Não sei se você prestou atenção, mas SO (krom) é igual a P quando a primeira ordem é universal; de fato, você pode expressar um problema NP-completo se adicionar uma variável existente de primeira ordem. (Não me lembro do exemplo que tive antes, posso tentar pesquisá-lo, se você quiser)

Não sei o que essa recuperação sintática se tornaria para a lógica de ordem alta ou de ordem variável ... o que quero dizer é que você também deve pensar em uma boa maneira de restringir quantificadores, porque restringir apenas a parte livre de quantificador não é útil ( pelo menos para fórmulas Krom)

Arthur MILCHIOR
fonte
1
Obrigado pela compreensão. Isso definitivamente requer mais reflexão!
András Salamon