Os conjuntos NP completos são formados a partir de dois outros conjuntos apenas se pelo menos um for NP-hard?

Essa pergunta é um pouco contrária a uma pergunta anterior sobre conjuntos formados a partir de operações de conjunto em conjuntos NP-completos:

Se o conjunto resultante da união, interseção ou produto cartesiano de dois conjuntos decidíveis e for NP completo, é pelo menos um de necessariamente NP rígido? Eu sei que eles não podem estar em P (assumindo P! = NP), pois P é fechado nessas operações definidas. Eu também sei que as condições de "decidível" e "NP-rígido" são necessárias, pois se considerarmos qualquer conjunto NP completo e outro conjunto fora do NP (seja NP-rígido ou indecidível), podemos formar dois novos Os conjuntos NP-hard não estão no NP cuja interseção é NP-complete. Por exemplo: e . No entanto, não sei como proceder depois disso. $L_1$ $L_2$ $L_1, L_2$ $L$ $B$ $L_1:= 01L \cup 11B$ $L_2:= 01L \cup 00B$

Estou pensando que o caso da união pode não ser verdade, pois podemos tomar um conjunto NP-completos e realizar a construção no Teorema de Ladner para obter um conjunto NPI que é um subconjunto de . Então é o conjunto NP completo original. No entanto, não sei se ainda está no NPI ou no NP-hard. Nem sei por onde começar para o caso de interseção e produto cartesiano. $A$ $B \in$ $A$ $B \cup (A \setminus B) = A$ $A \setminus B$

complexity-theory np-hard np np-intermediate Ari
fonte

Um problema em P pode ser NP completo se P = NP, o que faz com que sua afirmação "eles não possam estar em P" seja falsa.

Wojowu

@Wojowu Obrigado, você está correto. Apenas presumi que se entendesse que toda essa questão se baseia na premissa de que P! = NP. Caso contrário, não tem sentido / é trivial, pois teríamos NPC = P. Editarei a pergunta.

Ari

@Ari, na verdade , mesmo que .

N P C \neq P

$NPC\not = P$

P = N P

$P=NP$

Tom van der Zanden

@TomvanderZanden Como isso é possível? portanto, se P = NP, todos os problemas no NP podem ser resolvidos em tempo polinomial, incluindo problemas no NPC.

N P C \subseteq N P

$NPC \subseteq NP$

Ari #

@Ari O conjunto vazio e o conjunto de todas as strings estão no , mas não estão completos no . Você não pode reduzir nada ao conjunto vazio (ou conjunto de todas as strings) porque é sempre uma instância não (resp. Yes).

N P

$NP$

N P

$NP$

Tom van der Zanden

Respostas:

A interseção de duas linguagens não-NP-hard pode ser NP-hard. Exemplo: As soluções de qualquer instância 3SAT são a interseção definida das soluções de uma instância HORN-3SAT e uma instância ANTIHORN-3SAT. Isso ocorre porque uma cláusula 3CNF deve ser uma cláusula Horn ou anti-Horn e uma instância 3SAT é a conjunção de tais cláusulas. 3SAT é claro que NP-completo; HORN-3SAT e ANTIHORN-3SAT estão ambos em P.

Kyle Jones
fonte

Não posso seguir o seu exemplo. A interseção de Horn-SAT e ANTIHORN-SAT é uma linguagem chata bonita que está definitivamente em P.

Yuval Filmus

O HORN-3SAT pode ser definido de várias maneiras. Uma maneira é corrigir uma codificação de instâncias do HORN-3SAT - cada string codifica alguma dessas instâncias - e, em seguida, o HORN-3SAT consiste em instâncias satisfatórias. Essa codificação provavelmente é diferente da que você usaria para ANTIHORN-3SAT, portanto, não está claro qual é exatamente a linguagem de interseção - definitivamente não é SAT.

Yuval Filmus

Outra possibilidade é definir o HORN-3SAT como o idioma das instâncias do 3SAT que são (i) na forma de Horn, (ii) satisfatórias. Agora, a interseção de HORN-3SAT e ANTIHORN-3SAT faz sentido: consiste em todas as instâncias 3SAT que são (i) nas formas Horn e anti-Horn, (ii) satisfatórias. Isso só pode ser mais fácil que o HORN-3SAT e o ANTIHORN-3SAT.

Yuval Filmus

Essa é uma definição muito estranha de interseção de linguagem, diferente da que foi feita aqui. Se

são idiomas (como 3SAT), por sua interseção, queremos dizer

L_{1}

$L_1$

L_{2}

$L_2$

L_{1} \cap L_{2}

$L_1 \cap L_2$

Yuval Filmus

@ KyleJones @ Yuval Acho que pode haver alguma confusão em relação a instâncias versus idiomas. Enquanto cada instância de 3SAT é certamente composto unicamente de cláusulas de Horn e cláusulas anti-Horn, é não o caso que a língua

é igual a

ou, alternativamente,

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}$

uma vez que estes conjuntos têm cada instâncias compostasunicamentede cláusulas de Horn ou cláusulas Anti-Horn enquanto que cada instância de 3SAT pode ter uma mistura destes dois tipos de cláusulas ..

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