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

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.

Não é possível mostrar que um problema é sem separar P a partir de N P .$\mathsf{NPI}$$\mathsf{P}$$\mathsf{NP}$

Existem problemas artificiais que podem ser comprovados para estar em usando generalizações do teorema de Lander (ver também presente ) assumindo que N P ≠ P .$\mathsf{NPI}$$\mathsf{NP}\neq\mathsf{P}$

Também versão acolchoado de problemas são N P $\mathsf{NEXP\text{-}complete}$$\mathsf{NPI}$ assumindo (ver também este e este ).$\mathsf{NEXP} \neq \mathsf{EXP}$

Um problema em é frequentemente conjecturado como N P I quando:$\mathsf{NP}$$\mathsf{NPI}$

1. podemos mostrar, sob premissas razoáveis, que não é mas não se sabe que ele esteja em P ,$\mathsf{NPC}$$\mathsf{P}$

2. podemos mostrar, sob premissas razoáveis, que ele não está em mas não se sabe que está em N P C ,$\mathsf{P}$$\mathsf{NPC}$

e, por vezes apenas quando não podemos demonstrar que é em ou P .$\mathsf{NPC}$$\mathsf{P}$

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 $\mathsf{NPC}\not \subseteq \mathsf{P}$$\mathsf{P}$$\mathsf{P}$$\mathsf{NP}$

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 $\mathsf{NP}$$\mathsf{coNP}$$\mathsf{coAM}$$\mathsf{NP}$

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$$\omega(\log n)$$n^{O(1)}$$\log n$$O(\log^2 n)$

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 )$NP$$\exp(n^{O(1)})$