Problemas NP-completos não "obviamente" em NP

27

Ocorreu a muitos que em todas as provas de integridade de que li (que me lembro), é sempre trivial mostrar que existe um problema em e mostrando que é -hard é a ... parte mais difícil. Quais problemas -completos são esses cujos verificadores de tempo polinomial são altamente não triviais? $\textbf{NP}$ $\textbf{NP}$ $\textbf{NP}$ $\textbf{NP}$

complexity-theory np-complete np Gardenhead
fonte

9

Não é NP completo, mas mostrar a participação no NP de testar se um número é primo não é trivial (em vez de mostrar que é um composto, o que é trivial). É claro que o problema já está em P agora, mas ainda assim, este é um verificador intrigante.

Shaull

2

Provar que o "PRIME" está no NP foi definitivamente muito mais difícil do que provar que a maioria dos problemas completos do NP está no NP.

gnasher729

11

Consulte também a pergunta mais geral cstheory.stackexchange.com/q/21106/109 em CS.SE.

András Salamon

19

Existem pelo menos quatro desses completos de listados no apêndice de COMPUTADORES E INTRACTABILIDADE de Garey and Johnson : Um Guia para a Teoria da Completude de PN . $NP$

[AN6] NÃO DIVISIBILIDADE DE UM POLINOMIAL DE PRODUTO

INSTANCE: Sequências de pares de números inteiros , com cada e um número inteiro . $A_i = \langle (a_i[1],b_i[1]), ..., (a_i[k],b_i[k]) \rangle,\ 1 \leqslant i \leqslant m,$ $b_i[j] \geqslant 0,$ $N$

PERGUNTA: não é divisível por ? $\displaystyle \prod_{i=1}^m \left( \displaystyle\sum_{j=1}^k a_i[j] \cdot z^{b_i[j]} \right)$ $z^N - 1$

Referência: [Plaisted, 1977a] , [Plaisted, 1977b] . Transformação da 3SAT. A prova de associação ao NP não é trivial e aparece na segunda referência.

Os outros três que encontrei no apêndice são:

[OA13] LÓGICA MODAL S5 - SATISFIABILIDADE
[OA19] INSTALAÇÃO DE SEGUNDA ORDEM
[MS3] NÃO VIDA DE REDES DE PETRI DE ESCOLHA GRATUITA

Kyle Jones
fonte

Obrigado! Eu tenho este livro, por isso não deixo de conferir.

gardenhead

Eu sou um pouco incerto sobre esse problema: (1) Estou correto ao interpretar z é uma variável que pode receber qualquer valor inteiro (assim como uma equação linear / quadrática comum). (2) Assim, a não-divisibilidade seria equivalente a afirmar que: "para nenhum valor inteiro da equação z A é divisível por B"?

TheoryQuest1

11

O que reuni ao examinar as duas primeiras páginas do artigo de 1977a é que é uma quantidade relacionada ao número de zeros do polinômio que faz parte da entrada. Por mais que isso, você terá que vasculhar o jornal, receio.

z

$z$

Kyle Jones

4

Aqui está um problema da teoria do banco de dados, mais especificamente, da teoria da serialização.

Em Serializability by Locking (Página 237) , diz que

Quanto à complexidade da segurança, Papadimitriou et al. [14] mostraram que é -hard para testar se um sistema de transações não é seguro para e conjecturou que o problema é . Do Teorema 3 (neste artigo), segue-se que isso é verdade. $\textrm{NP}$ $SSR$ $\textrm{NP}$

O problema de segurança pode ser encontrado no artigo "Alguns problemas computacionais relacionados ao controle de simultaneidade de bancos de dados", de Papadimitriou et al. Infelizmente, não tenho acesso a ele. $SSR$

hengxin
fonte

2

Para mim, a Programação Linear Inteira (e a Aritmética do Pré -burgador Livre de Quantificador relacionada) estão nesta classe.

Uma abordagem ingênua para um problema de ILP dimensional é iterar por todos os vetores inteiros de comprimento . Mas este é um processo ilimitado. $n$ $n$

Você precisa usar alguma teoria dos números para provar que existe um limite superior polinomial no tamanho das soluções, o que significa que, se existir uma solução, sempre haverá uma solução de tamanho polinomial, que atua como um certificado.

Mais informações podem ser encontradas na resposta a uma pergunta que fiz há algum tempo.

jmite
fonte

Problemas NP-completos não "obviamente" em NP

Respostas: