Existem problemas de NP, não em P e nem NP Complete?

Existem problemas conhecidos em (e não em ) que não são completos? Meu entendimento é que atualmente não há problemas conhecidos, mas não foi descartada como uma possibilidade. P N $\mathsf{NP}$$\mathsf{P}$$\mathsf{NP}$

Se houver um problema (e não ), mas não , isso seria resultado de nenhum isomorfismo existente entre as instâncias desse problema e o conjunto ? Nesse caso, como saberíamos que o problema não é 'mais difícil' do que o que identificamos atualmente como o conjunto ?P N P - c o m p L e T e N P - c o m p L e T e N P N P - c o m p L e T $\mathsf{NP}$$\mathsf{P}$$\mathsf{NP\text{-}complete}$$\mathsf{NP\text{-}complete}$$\mathsf{NP}$$\mathsf{NP\text{-}complete}$

Existem problemas conhecidos no NP (e não no P) que não são NP Complete? Meu entendimento é que atualmente não há problemas conhecidos, mas não foi descartada como uma possibilidade.

Não, isso é desconhecido (com exceção dos idiomas triviais e Σ ∗ , esses dois não estão completos devido à definição de muitas reduções de uma, geralmente essas duas são ignoradas ao considerar reduções de uma). Existência de uma N P problema que não é completo para N P wrt muitos-ona reduções de tempo polinomial implicaria que P ≠ N P que não é conhecida (embora amplamente acreditado). Se as duas classes são diferentes, então sabemos que há problemas na N P que não estão completos para ele, tomar qualquer problema em P .$\emptyset$$\Sigma^*$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{P}\neq\mathsf{NP}$$\mathsf{NP}$$\mathsf{P}$

Se houver um problema NP (e não P), mas não NP Complete, isso seria resultado de nenhum isomorfismo existente entre as instâncias desse problema e o conjunto NP Complete?

Se as duas classes de complexidade são diferentes, então pelo Teorema de Ladner há problemas que são Intermédio, ou seja, são entre P e N P - c o m p L e T e .$\mathsf{NP}$$\mathsf{P}$$\mathsf{NP\text{-}complete}$

Nesse caso, como saberíamos que o problema do NP não é "mais difícil" do que o que atualmente identificamos como o conjunto NP Complete?

Eles são ainda redutível tempo polinomial para problemas de modo que não pode ser mais difícil do que N P - c o m p L e T e problemas.$\mathsf{NP\text{-}complete}$$\mathsf{NP\text{-}complete}$

Como @Kaveh afirmou, essa pergunta só é interessante se assumirmos que ; o resto da minha resposta toma isso como uma suposição e, principalmente, fornece links para aumentar ainda mais seu apetite. Sob essa hipótese, pelo teorema de Ladner sabemos que há problemas que não são nem em P nem N P C ; estes problemas são chamados N P Intermédio ou N P I . Curiosamente, o teorema de Ladner pode ser generalizado para muitas outras classes de complexidade para produzir problemas intermediários semelhantes. Além disso, o teorema também implica que existe uma hierarquia infinita$P \neq NP$$P$$NPC$$NP$$NPI$de problemas intermediários que não são redutíveis-tempo poli uns aos outros em .$NPI$

Infelizmente, mesmo com a suposição , é muito difícil encontrar problemas naturais que seriam prováveis N P I (é claro que você tem problemas artificiais provenientes da prova do teorema de Ladner). Assim, mesmo assumindo P ≠ N P neste momento, só podemos acreditar que alguns problemas são N P I, mas não provam isso. Chegamos a essas crenças quando temos evidências razoáveis ​​para acreditar que um problema de N P não está em N P C e / ou não em $P \neq NP$$NPI$$P \neq NP$$NPI$$NP$$NPC$$P$; ou apenas quando foi estudado por um longo tempo e evitou se encaixar em qualquer uma das classes. Há uma lista bastante abrangente de tais problemas nesta resposta . Inclui os favoritos de todos os tempos, como fatoração, log discreto e isomorfismo gráfico.

Curiosamente, alguns desses problemas (notáveis: fatoração e log discreto) têm soluções de tempo polinomial em computadores quânticos (ou seja, estão em ). Alguns outros problemas (como o isomorfismo do gráfico) não são conhecidos em B Q P , e há pesquisas em andamento para resolver a questão. Por outro lado, suspeita-se que N P C ⊈ B Q P , portanto, as pessoas não acreditam que teremos um algoritmo quântico eficiente para SAT (embora possamos obter uma velocidade quadrática); é uma questão interessante se preocupar com que tipo de estrutura os problemas de precisam para estar no .$BQP$$BQP$$NPC \not\subseteq BQP$B Q $NPI$$BQP$

Nenhuma NP problemas -completo são conhecidos por serem em P . Se houver um algoritmo de tempo polinomial para qualquer problema completo de NP , então P = NP , porque qualquer problema em NP tem uma redução de tempo polinomial para cada problema de NP completo. (Na verdade, é assim que " NP- complete" é definido.) E, obviamente, se todo problema de NP- complete estiver fora de P , isso significa que P ≠ NP . Não sabemos ao certo por que é difícil mostrar de uma maneira ou de outra; se soubéssemos a resposta para essa pergunta, provavelmente saberíamos muito mais sobre P eNP . Temos algumas técnicas de prova que sabemos que não funcionam (relativização e provas naturais, por exemplo), mas não temos uma explicação de princípio sobre por que esse problema é difícil.

Se há problemas em NP que não estão em P , na verdade há uma hierarquia infinita de problemas em NP entre aqueles em P e aqueles que são NP completos: esse é um resultado chamado teorema de Ladner .

Espero que isto ajude!

$P$

$P$$P$

$P$

¹ Problema semelhante: o isomorfismo do subgrafo é NP-Complete em sentido forte.