Participação não trivial em NP

Existe um exemplo de uma linguagem que está em $NP$ , mas onde não podemos provar este fato diretamente ao mostrar que existe uma testemunha polinomial para a adesão nesta língua?

Em vez disso, o fato de o idioma estar no seria comprovado reduzindo-o para outro idioma no , onde o vínculo entre os dois não é trivial e requer uma análise cuidadosa.$NP$$NP$

De maneira mais geral, existem alguns exemplos interessantes de problemas no para que seja difícil perceber que eles estão no ?$NP$$NP$

Uma semi-resposta seria o problema de decidir o vencedor em jogos de paridade: para mostrar que ele está em (mesmo ), precisamos do teorema da determinação posicional que é profundo e não trivial. No entanto, essa resposta não é ideal, porque ainda se resume à existência de uma testemunha polinomial para esse problema exato (a estratégia posicional) e não se reduz a outro problema diferente .$NP$$NP\cap coNP$$NP$

Outro seria o algoritmo de primalidade da AKS: decidir se um número é primo é polinomial, enquanto não há, a priori, uma pequena testemunha desse fato. Digamos que excluamos os "algoritmos polinomiais surpreendentes", pois muitos deles se encaixariam na descrição acima. Estou mais interessado em algoritmos surpreendentes que não são determinísticos.$NP$

Programação Inteira .

Mostrando que, se houver uma solução inteira, existe uma solução inteira de tamanho polinomial bastante envolvida. Vejo

• Christos Papadimitriou, " Sobre a complexidade da programação inteira ", JACM, 1981.

Enquanto o problema "é o número de cruzamento de um gráfico no máximo ?" é trivial em NP, a associação NP dos problemas relacionados ao número de cruzamento retilíneo e ao número de cruzamento de pares não é altamente óbvia; cf. Bienstock, Alguns problemas provavelmente difíceis de cruzar números, Computação Discreta. Geometry 6 (1991) 443-459, e Schaefer et al., Reconhecendo gráficos de cordas em NP, J. Comput. Sci do sistema 67 (2003) 365-380.$k$

Meu exemplo favorito é um resultado clássico de 1977 de Ashok Chandra e Philip Merlin. Eles mostraram que o problema de contenção de consultas era decidível para consultas conjuntivas. O problema de contenção de consulta conjunta acaba sendo equivalente a decidir se existe um homomorfismo entre as duas consultas de entrada. Isso reformula um problema semântico, envolvendo quantificação em um conjunto infinito, em um problema sintático, exigindo apenas a verificação de um número finito de possíveis homomorfismos. O certificado de homomorfismo é apenas de tamanho linear e, portanto, o problema está no NP.

Esse teorema fornece um dos fundamentos da teoria da otimização de consultas ao banco de dados. A idéia é transformar uma consulta em outra, mais rápida. No entanto, deseja-se garantir que o processo de otimização não crie uma nova consulta que não forneça respostas em alguns bancos de dados em que a consulta original produziu resultados.

Formalmente, uma consulta ao banco de dados é uma expressão do formulário , onde x é uma lista de variáveis ​​livres, y é uma lista de variáveis ​​vinculadas e Q ( x , y ) é uma fórmula de primeira ordem com variáveis x e y de um idioma com símbolos de relação. A consulta Q pode conter quantificadores existenciais e universais, a fórmula pode conter conjunção e disjunção de átomos relacionais e a negação também pode aparecer. Uma consulta é aplicada a uma instância de banco de dados $\mathbf{x}.Q(\mathbf{x},\mathbf{y})$$\mathbf{x}$$\mathbf{y}$$Q(\mathbf{x},\mathbf{y})$$\mathbf{x}$$\mathbf{y}$$Q$$I$, que é um conjunto de relações. O resultado é um conjunto de tuplas; quando tupla no resultado é substituído por $\mathbf{t}$$\mathbf{x}$ , a fórmula pode ser satisfeita. Pode-se então comparar duas consultas: Q 1 está contida em Q 2 se sempre que Q 1 aplicado a um banco de dados arbitrária exemplo I produz alguns resultados, então Q 2 aplicado ao mesmo exemplo que também produz alguns resultados. (Tudo bem se Q 1 não produzir resultados, mas Q $Q(\mathbf{t},\mathbf{y})$$Q_1$$Q_2$$Q_1$$I$$Q_2$$I$$Q_1$$Q_2$mas, para contenção, a implicação deve ser mantida para todas as instâncias possíveis.) O problema de contenção de consulta pergunta: dadas duas consultas ao banco de dados e Q 2 , Q 1 está contido em Q 2 ?$Q_1$$Q_2$$Q_1$$Q_2$

Não ficou claro diante de Chandra-Merlin que o problema era decidível. Usando apenas a definição, é preciso quantificar o conjunto infinito de todos os bancos de dados possíveis. Se as consultas são irrestritas, então o problema é, na verdade, undecidable: deixe ser uma fórmula que é sempre verdadeiro, então Q 1 está contida em Q 2 sse Q 2 é válido. (Este é o problema de Hilts , Entscheidung , mostrado indecidível por Church e Turing em 1936.)$Q_1$$Q_1$$Q_2$$Q_2$

Para evitar indecidibilidade, uma consulta conjuntiva tem uma forma bastante limitada: contém apenas quantificadores existenciais, e negação e disjunção não são permitidas. Então Q é uma fórmula existencial positiva com apenas conjunção de átomos relacionais. Este é um pequeno fragmento de lógica, mas é suficiente para expressar uma grande proporção de consultas úteis ao banco de dados. A declaração clássica no SQL expressa consultas conjuntivas; a maioria das consultas de mecanismos de pesquisa é conjunta.$Q$$Q$SELECT ... FROM

Pode-se definir homomorfismos entre consultas de maneira direta (semelhante ao homomorfismo de gráfico, com um pouco de contabilidade extra). O teorema de Chandra-Merlin diz: dadas duas consultas conjuntivas e Q 2 , Q 1 está contida em Q 2 se houver um homomorfismo de consulta de Q 2 a Q 1 . Isso estabelece a associação ao NP e é fácil mostrar que isso também é difícil para o NP.$Q_1$$Q_2$$Q_1$$Q_2$$Q_2$$Q_1$

• Ashok K. Chandra e Philip M. Merlin, Implementação Ótima de Consultas Conjuntivas em Bases de Dados Relacionais , STOC '77 77–90. doi: 10.1145 / 800105.803397

Decidibilidade de contenção consulta foi mais tarde estendido para uniões de consultas conjuntivo (consultas positivos existenciais onde disjunção é permitido), embora permitindo disjunção aumenta a complexidade para -completo. Também foram estabelecidos resultados de decidibilidade e indecidibilidade para uma forma mais geral de contenção de consultas , envolvendo avaliações semirráficas que ocorrem ao contar o número de respostas, ao combinar anotações na proveniência ou ao combinar resultados de consultas em bancos de dados probabilísticos.$\Pi^P_2$

Encontrei um bom candidato ao ler alguns artigos sobre equações diofantinas quadráticas:

JC Lagarias, Certificados sucintos de soluções para equações diofantinas quadráticas binárias (2006)

A partir do resumo: ... Seja o comprimento da codificação binária da equação diofantina quadrática binária F dada por a x 2 1 + b x 1 x 2 + c $L(F)$$F$. Suponha queFé uma equação que possui uma solução inteira não negativa. Este documento mostra que existe uma prova (ou seja, "certificado") de queFpossui uma solução que pode ser verificada$a x_1^2 +b x_1 x_2+ c x_2^2 +d x_1+e x_2 + f = 0$$F$$F$Operações de bits O ( L ( F ) 5 log L ( F ) log log L ( F ) ) . Um corolário desse resultado é que o conjunto Σ = { F : F  possui uma solução inteira não negativa } está na classe de complexidade NP ...$O(L(F)^5 \log L(F) \log \log L(F))$$\Sigma = \{F : F \text{ has a nonnegative integer solution}\}$

... mas - para ser sincero - a única evidência que tenho de que não é trivial é o número de páginas do artigo ... 62! :-)

Quando o reconhecimento do reconhecimento do gráfico de tolerância foi aberto, o seguinte artigo mostrou que ele está em NP:

http://www.sciencedirect.com/science/article/pii/S0166218X04000940

(Posteriormente, o reconhecimento do gráfico de tolerância mostrou-se NP completo: http://arxiv.org/abs/1001.3251 )

Decidir a acessibilidade para vários tipos de sistemas de estado infinito às vezes é decidível, geralmente não. Para alguns casos especiais interessantes, sempre existe um certificado pequeno o suficiente e verificável com eficiência, colocando esses problemas no NP. Aqui está um tratamento elegante para autômatos paramétricos de um contador:

• Christoph Haase, Stephan Kreutzer, Joël Ouaknine, James Worrell, Acessibilidade em autômatos sucintos e paramétricos de balcão único, CONCUR 2009, LNCS 5710 369–383. doi: 10.1007 / 978-3-642-04081-8_25 ( versão estendida )

$NP$$L_1, L_2$$L_1\in NP$$L_2\notin NP$$L$

$L\in NP$$L\in NP$$NP$ , eleva-se a resolver o famoso números primos gémeos conjectura, por isso é certamente não trivial ...