Digamos que un lenguaje está cerca de la densidad P si hay un algoritmo de tiempo polinómico que decide correctamente en casi todas las entradas.
Tenga en cuenta que no tiene que ser escaso. Por ejemplo, si tiene cadenas de bits, entonces sigue desapareciendo (a una tasa exponencial), ya que .
De acuerdo con la definición anterior, no es difícil (artificialmente) construir problemas completos de NP que estén cerca de la densidad de P. Por ejemplo, deje que sea cualquier lenguaje NP completo y defina . Entonces retiene NP- completitud, pero tiene como máximo -bit yes-instancia. Por lo tanto, el algoritmo trivial que responde "no" a cada entrada, decidirá correctamente en casi todas las entradas; errará solo en una fracción de entradas de bits.
Por otro lado, sería muy sorprendente si todos los problemas completos de NP están cerca de la densidad de P. Significaría que, en cierto sentido, todos los problemas completos de NP son casi fáciles. Esto motiva la pregunta:
Suponiendo P NP , ¿cuáles son algunos problemas naturales de NP completos que no están cerca de la densidad de P ?
fuente
Respuestas:
Investigué si existe una hipótesis generalmente aceptada en la teoría de la complejidad, lo que implica que debe existir un lenguaje NP completo que no pueda aceptarse en tiempo polinómico en casi todas las entradas (como se define en la pregunta).
Curiosamente, las hipótesis más "estándar" no parecen implicarlo. Es decir, no parece seguir (a menos que haya pasado por alto algo) de P NP , P BPP , NP coNP , E NE , EXP NEXP , NP PSPACE , NP EXP , NP P / poly, PH no colapsa, etc.≠ = ≠ ≠ ≠ ≠ ≠ ⊈
Por otro lado, encontré una hipótesis, un poco menos estándar, que implica la existencia del problema NP buscado completo, aunque no es natural. En la teoría de la medida limitada por los recursos, la hipótesis fundamental es que NP no tiene -medida cero, denotada por NP . Informalmente, esto significa que los idiomas NP dentro de E no forman un subconjunto insignificante. Para más detalles, vea una encuesta aquí . En esta teoría prueban, entre muchas otras cosas, que NP implica la existencia de una Pp μp( )≠0 μp( )≠0 -bi-lenguaje inmune en NP . Un lenguaje es P -bi-inmune si ninguno ni su complemento tiene un subconjunto infinito en P . Tal lenguaje satisface nuestros requisitos de una manera fuerte.L L
Sin embargo, aún no está claro si existe un ejemplo que represente un problema natural .
fuente