Un lenguaje completo NP denso implica P = NP

Decimos que el lenguaje es denso si existe un polinomio tal que para todo En otras palabras, para cualquier longitud dada sólo existen polinomialmente muchas palabras de longitud que no están en $J \subseteq \Sigma^{*}$ $p$

| J^{c} \cap Σ^{n} | \leq p (n)

$|J^c \cap \Sigma^n| \leq p(n)$

n \in N .

$n \in \mathbb{N}.$

n

$n$

n

$n$

J .

$J.$

El problema que estoy estudiando actualmente pide mostrar lo siguiente

Si existe un lenguaje denso completo, entonces $NP$ $P = NP$

Lo que sugiere el texto es considerar la reducción del polinomio a - y luego construir un algoritmo que intente satisfacer la fórmula dada al mismo tiempo que genera elementos en $3$ $SAT$ $CNF$ $J^c.$

Lo que me pregunto es

¿Hay alguna prueba más directa? ¿Se conoce esta noción en un entorno más general?

complexity-theory time-complexity np-complete satisfiability Jernej
fuente

Existe una noción relacionada de idiomas dispersos , en la que la condición es todo lo contrario:

| J \cap Σ^{n} | \leq p (n)

$|J \cap \Sigma^n| \leq p(n)$

Yuval Filmus

Mira el teorema de Mahaney .

Pål GD

@ PålGD ¿Convertir en una respuesta? (suponiendo que el argumento se traslade a idiomas densos)

Yuval Filmus

Respuestas:

Este es un buen problema de tarea sobre el teorema de Mahaney.

Tenga en cuenta que el complemento de un lenguaje "denso" es un lenguaje escaso. Además, si un lenguaje es -completo, su complemento es $\mathsf{NP}$ $\mathsf{coNP}$ completo.

Si hay un lenguaje completo "denso" , hay un escaso $\mathsf{NP}$ $\mathsf{coNP}$ lenguaje -Complete.

El teorema de Mahaney nos dice que no hay un lenguaje completo escaso a menos que $\mathsf{NP}$ $\mathsf{P}=\mathsf{NP}$ .

Podemos adoptar la prueba para mostrar que no hay un lenguaje completo escaso menos que que sea equivalente a (ya que $\mathsf{coNP}$ $\mathsf{P}=\mathsf{coNP}$ $\mathsf{P}=\mathsf{NP}$ $\mathsf{P}$ está cerrado bajo complementos).

En resumen, la respuesta es no menos que . Tenga en cuenta que si entonces cada lenguaje no trivial es $\mathsf{P}=\mathsf{NP}$ $\mathsf{P}=\mathsf{NP}$ $\mathsf{NP}$ -completo.

PD: Es posible que desee probar el siguiente y luego usar el teorema de Mahaney: hay una escasa conjunto -Complete si y sólo si existe una escasa conjunto -Complete. Sin embargo, dudo que una prueba de esta afirmación sea mucho más fácil que una prueba del teorema de Mahaney. $\mathsf{NP}$ $\mathsf{coNP}$

Kaveh
fuente

Como se mencionó anteriormente de acuerdo con el teorema de Mahaney . Los idiomas escasos y densos no pueden ser menos que $NP-Hard$ $P=NP$ .

El borrador mencionado contiene la prueba completa.

Reza
fuente

Esto no da más que el comentario (que ni siquiera es tuyo). Por favor, explique para hacer una respuesta adecuada de esta publicación.

Raphael

@Raphael: Es una respuesta adecuada. ¿Revisaste el enlace?

Tsuyoshi Ito

@TsuyoshiIto: las respuestas que consisten solo en un enlace generalmente se consideran malas en SE; ver aquí .

Raphael

@Raphael: La pregunta respondida se resolvió antes en la literatura. El enlace contiene pruebas completas (que son 6 páginas). Creo que si tiene más preguntas podríamos continuar con la discusión.

Reza

@Raphael: tonto. Un enlace es mejor que nada. Si lo desea, elabore la respuesta usted mismo en lugar de culpar a un usuario por publicar un enlace útil.

Tsuyoshi Ito