¿Se forman conjuntos completos de NP a partir de otros dos conjuntos solo si al menos uno es NP-duro?

Esta pregunta es algo opuesta a una pregunta anterior sobre conjuntos formados a partir de operaciones de conjuntos en conjuntos completos de NP:

Si el conjunto resultante de la unión, intersección, o el producto cartesiano de dos conjuntos decidibles y es NP-completo, es decir, al menos uno de necesariamente NP-duro? Sé que ambos no pueden estar en P (suponiendo que P! = NP) ya que P está cerrado en estas operaciones establecidas. También sé que las condiciones de "decidible" y "NP-hard" son necesarias ya que si consideramos cualquier conjunto NP-completo y otro conjunto fuera de NP (ya sea NP-hard o indecidible) entonces podemos formar dos nuevos NP-hard establece no en NP cuya intersección es NP-completa. Por ejemplo: , y . Sin embargo, no sé cómo proceder después de eso. $L_1$ $L_2$ $L_1, L_2$ $L$ $B$ $L_1:= 01L \cup 11B$ $L_2:= 01L \cup 00B$

Estoy pensando que el caso de la unión podría no ser cierto ya que podemos tener un conjunto NP-completo y llevar a cabo la construcción en el teorema de Ladner para obtener un conjunto NPI, que es un subconjunto de . Entonces es el conjunto NP-completo original. Sin embargo, no sé si todavía está en NPI o NP-hard. Ni siquiera sé por dónde empezar para el caso de intersección y producto cartesiano. $A$ $B \in$ $A$ $B \cup (A \setminus B) = A$ $A \setminus B$

complexity-theory np-hard np np-intermediate Ari
fuente

Un problema en P puede ser NP-completo si P = NP, lo que hace que su reclamo "ambos no pueden estar en P" falso.

Wojowu

@Wojowu Gracias, tienes razón. Supuse que se entendía que toda esta pregunta se basa en la premisa de que P! = NP. De lo contrario, no tiene sentido / trivial ya que tendríamos NPC = P. Editaré la pregunta.

Ari

@Ari, en realidad , incluso si .

N P C \neq P

$NPC\not = P$

P = N P

$P=NP$

Tom van der Zanden

@TomvanderZanden ¿Cómo es eso posible? por lo que si P = NP, todos los problemas en NP pueden resolverse en tiempo polinómico, incluidos los problemas en NPC.

N P C \subseteq N P

$NPC \subseteq NP$

Ari

@Ari El conjunto vacío y el conjunto de todas las cadenas están en , pero no son completos. No puede reducir nada al conjunto vacío (o al conjunto de todas las cadenas) porque siempre es una instancia de no (resp. Sí).

N P

$NP$

N P

$NP$

Tom van der Zanden

Respuestas:

La intersección de dos lenguajes no NP-hard puede ser NP-hard. Ejemplo: Las soluciones de cualquier instancia de 3SAT son la intersección establecida de las soluciones de una instancia de HORN-3SAT y una instancia de ANTIHORN-3SAT. Esto se debe a que una cláusula 3CNF debe ser una cláusula Horn o anti-Horn y una instancia 3SAT es la conjunción de tales cláusulas. 3SAT es, por supuesto, NP-completo; HORN-3SAT y ANTIHORN-3SAT están ambos en P.

Kyle Jones
fuente

No puedo seguir tu ejemplo. La intersección de HORN-SAT y ANTIHORN-SAT es un lenguaje bastante aburrido que definitivamente está en P.

Yuval Filmus

HORN-3SAT se puede definir de muchas maneras. Una forma es arreglar una codificación de instancias HORN-3SAT, cada cadena codifica alguna instancia de este tipo, y luego HORN-3SAT consiste en instancias satisfactorias. Es probable que esta codificación sea diferente de la codificación que usaría para ANTIHORN-3SAT, por lo que no está claro cuál es exactamente el lenguaje de intersección, definitivamente no SAT.

Yuval Filmus

Otra posibilidad es definir HORN-3SAT como el lenguaje de las instancias 3SAT que están (i) en forma de Horn, (ii) satisfactoria. Ahora la intersección de HORN-3SAT y ANTIHORN-3SAT tiene sentido: consta de todas las instancias de 3SAT que son (i) en forma de Horn y anti-Horn, (ii) satisfactoria. Esto solo puede ser más fácil que cada uno de HORN-3SAT y ANTIHORN-3SAT.

Yuval Filmus

Esta es una definición muy extraña de intersección del lenguaje, diferente de la que se entiende aquí. Si y son idiomas (como 3SAT), por su intersección queremos decir .

L_{1}

$L_1$

L_{2}

$L_2$

L_{1} \cap L_{2}

$L_1 \cap L_2$

Yuval Filmus

@ KyleJones @ Yuval Creo que puede haber cierta confusión con respecto a las instancias frente a los idiomas. Mientras que cada instancia de 3SAT es, sin duda compuesta únicamente de cláusulas de Horn y cláusulas anti-Horn, es no el caso de que el idioma es igual a o bien ya que estos conjuntos tienen instancias cada una compuesta únicamente por cláusulas Horn o cláusulas Anti-Horn, mientras que cada instancia de 3SAT puede tener una mezcla de estos dos tipos de cláusulas ..

3 S A T

$\mathsf{3SAT}$

H O R N 3 S A T \cap A N T I H O R N 3 S A T

$\mathsf{HORN3SAT}\cap\mathsf{ANTIHORN3SAT}$

H O R N 3 S A T \cup A N T I H O R N 3 S A T

$\mathsf{HORN3SAT}\cup\mathsf{ANTIHORN3SAT}$

Ari