Por que os problemas de NPI não são da mesma complexidade?

11

Como se olha para um problema e o motivo pelo qual é provável NP-Intermediário em oposição a NP-Complete? Muitas vezes, é bastante simples olhar para um problema e dizer se é provável que o NP-Completo seja ou não, mas me parece muito mais difícil dizer se um problema é NP-Intermediário, pois a linha parece ser bastante fina entre os dois. Aulas. Basicamente, o que estou perguntando é por que um problema que pode ser verificado no tempo polinomial (se é que existe), mas não resolvido no tempo polinomial (desde que P não seja igual a NP) não seria redutível no tempo polinomial. Além disso, existe alguma maneira de mostrar que um problema é NP-Intermediário semelhante ao modo como um problema é mostrado como NP-Hard, como redução ou alguma outra técnica? Quaisquer links ou manuais que me ajudem a entender a classe do NP-Intermediate também serão apreciados.

Jesse Stern
fonte
2
"um problema que pode ser satisfeito em tempo polinomial", acho que você quer dizer "um problema que pode ser verificado em tempo polinomial".
Kaveh
2
Existe uma classe de problemas GI completos que são polinomialmente equivalentes ao isomorfismo do gráfico. O IG é um grande problema conjecturado como intermediário NP
Mohammad Al-Turkistany
1
Btw, o título é enganoso, a igualdade de dois problemas de complexidade com relação a uma redução (por exemplo, reduções de Karp) já está definida, eu sugiro que você mude para algo como "Por que os problemas de NPI não são da mesma complexidade?".
Kaveh
@kaveh Realizou todas as edições. Obrigado por outra ótima resposta!
Jesse Stern
1
"Geralmente, é bastante simples olhar para um problema e dizer se é provável que o NP-Complete seja ou não". IMHO, isso não poderia estar mais longe da verdade!
MCH

Respostas:

20

Não é possível mostrar que um problema é sem separar P a partir de N P .NPIPNP

Existem problemas artificiais que podem ser comprovados para estar em usando generalizações do teorema de Lander (ver também presente ) assumindo que N PP .NPINPP

Também versão acolchoado de problemas são N P INEXP-completeNPI assumindo (ver também este e este ).NEXPEXP

Um problema em é frequentemente conjecturado como N P I quando:NPNPI

  1. podemos mostrar, sob premissas razoáveis, que não é mas não se sabe que ele esteja em P ,NPCP

  2. podemos mostrar, sob premissas razoáveis, que ele não está em mas não se sabe que está em N P C ,PNPC

e, por vezes apenas quando não podemos demonstrar que é em ou P .NPCP

Um exemplo de suposição razoável é a hipótese de tempo exponencial (ou algumas de outras suposições de dureza computacional ).

Basicamente, o que estou perguntando é por que um problema que pode ser satisfeito no tempo polinomial (se houver), mas não resolvido no tempo polinomial (desde que P não seja igual a NP) não seria redutível no tempo polinomial.

P P N PNPCPPPNP

Kaveh
fonte
2
"2. podemos mostrar, sob suposições razoáveis, que não está em P, mas não se sabe que esteja em NP" Você não quer dizer "... em NPC"?
Tyson Williams
@ Victor, não, não se sabe que não é igual a , e eles são diferentes se e forem diferentes. Revertendo sua edição. N P C P N PPNPCPNP
Kaveh
@Kaveh, acho que ele estava pensando sobre as línguas triviais ( e ), mas você excluí-los do P.{ 0 , 1 } *{0,1}
didest
@ Diego, bem, nada é redutível para eles, mas você está certo. Eu vou consertar isso.
Kaveh
@ Kaveh e Diego: Sim, eu estava pensando sobre essas linguagens triviais.
Victor Stafusa
12

Um caso típico é quando um problema em também está em ou . Supondo que a hierarquia polinomial não diminua, esse problema não pode ser completo. Exemplos incluem fatoração de número inteiro, logaritmo discreto, isomorfismo de grafos, alguns problemas de treliça etc.c o N P c o A M N PNPcoNPcoAMNP

MCH
fonte
9

Outro caso típico de problema de é quando há uma testemunha de comprimento mas menor que . O problema da existência de um clique de tamanho em um gráfico é um exemplo típico - nesse caso, a testemunha (o clique específico) requer bits.ω ( log n ) n O ( 1 ) log n O ( log 2 n )NPIω(logn)nO(1)lognO(log2n)

Supondo a hipótese de tempo exponencial, esse problema é mais fácil do que um completo de (que requer tempo ), mas é mais difícil que um problema de tempo polinomial.exp ( n O ( 1 ) )NPexp(nO(1))

David Harris
fonte