Digamos que uma linguagem seja P -densidade perto se houver um algoritmo de tempo polinomial que decida corretamente em quase todas as entradas.
Observe que não precisa ser esparso. Por exemplo, se tiver bits, ainda estará desaparecendo (a uma taxa exponencial), já que .
Não é difícil (artificialmente) construir problemas completos de NP com fechamento de densidade P , de acordo com a definição acima. Por exemplo, seja qualquer idioma completo de NP e defina . Então mantém a complexidade NP , mas tem no máximo bits sim instâncias. Portanto, o algoritmo trivial que responde "não" a todas as entradas decide corretamente em quase todas as entradas; ele irá errar apenas em uma fração das entradas de bits.
Por outro lado, seria muito surpreendente se todos os problemas completos de NP estivessem próximos à densidade de P. Isso significaria que, de certa forma, todos os problemas completos de NP são quase fáceis. Isso motiva a pergunta:
Supondo P NP , quais são alguns problemas naturais completos de NP que não são próximos à densidade de P ?
fonte
Respostas:
Examinei se existe uma hipótese geralmente aceita na teoria da complexidade, o que implica que deve existir uma linguagem completa NP que não possa ser aceita em tempo polinomial em quase todas as entradas (conforme definido na pergunta).
Curiosamente, as hipóteses mais "padrão" não parecem implicar isso. Ou seja, ele não parece seguir (a menos que eu tenha esquecido alguma coisa) de P NP , P BPP , NP coNP , E NE , EXP NEXP , NP PSPACE , NP EXP , NP P / poli, PH não diminui, etc.≠ = ≠ ≠ ≠ ≠ ≠ ⊈
Por outro lado, encontrei uma hipótese, um pouco menos padrão, que implica a existência do problema completo de NP procurado , embora não seja natural. Na teoria da medida limitada a recursos, a hipótese fundamental é que NP não possui medida zero, denotada por NP . Informalmente, isso significa que os idiomas NP em E não formam um subconjunto desprezível. Para detalhes, consulte uma pesquisa aqui . Nesta teoria, eles provam, entre muitas outras coisas, que NP implica a existência de um Pp μp( )≠0 μp( )≠0 linguagem imuno-imune em PN . Uma linguagem é P -bi-imune se nem nem seu complemento tem um subconjunto infinito em P . Essa linguagem satisfaz nossos requisitos de maneira forte.L L
No entanto, ainda não está claro se existe um exemplo que represente um problema natural .
fonte