Les ensembles NP-complets sont-ils formés à partir de deux autres ensembles uniquement si au moins un est NP-dur?

Cette question est en quelque sorte l'inverse d' une question précédente sur les ensembles formés à partir d'opérations sur les ensembles NP-complets:

Si l'ensemble résultant de l'union, de l'intersection ou du produit cartésien de deux ensembles décidables et est NP-complet, au moins l'un de nécessairement NP-dur? Je sais qu'ils ne peuvent pas être tous les deux dans P (en supposant P! = NP) puisque P est fermé sous ces opérations d'ensemble. Je sais également que les conditions de «décidable» et de «NP-difficile» sont nécessaires car si nous considérons tout ensemble NP complet et un autre ensemble dehors de NP (que ce soit juste NP-difficile ou indécidable), alors nous pouvons former deux nouveaux Ensembles NP-hard non dans NP dont l'intersection est NP-complete. Par exemple: $L_1$ $L_2$ $L_1, L_2$ $L$ $B$ et . Cependant, je ne sais pas comment procéder après cela. $L_1:= 01L \cup 11B$ $L_2:= 01L \cup 00B$

Je pense que le cas de l' union peut - être pas vrai que nous pouvons prendre un ensemble NP-complet et effectuer la construction dans le théorème de Ladner pour obtenir un ensemble NPI qui est un sous - ensemble de . Alors est l'ensemble NP-complet d'origine. Cependant, je ne sais pas si est toujours en NPI ou NP-hard. Je ne sais même pas par où commencer pour le cas de l'intersection et du produit cartésien. $A$ $B \in$ $A$ $B \cup (A \setminus B) = A$ $A \setminus B$

complexity-theory np-hard np np-intermediate Ari
la source

Un problème dans P peut être NP-complet si P = NP, ce qui fait que votre affirmation "ils ne peuvent pas être tous les deux dans P" est fausse.

Wojowu

@Wojowu Merci, vous avez raison. J'ai juste supposé qu'il était entendu que toute cette question est basée sur la prémisse que P! = NP. Sinon, c'est vide de sens / trivial puisque nous aurions alors NPC = P. Je modifierai la question.

Ari

N P C \neq P

$NPC\not = P$

P = N P

$P=NP$

N P C \subseteq N P

$NPC \subseteq NP$

N P

$NP$

N P

$NP$

Réponses:

L'intersection de deux langues non NP-hard peut être NP-hard. Exemple: Les solutions de toute instance 3SAT sont l'intersection définie des solutions d'une instance HORN-3SAT et d'une instance ANTIHORN-3SAT. En effet, une clause 3CNF doit être une clause Horn ou anti-Horn et une instance 3SAT est la conjonction de ces clauses. 3SAT est bien sûr NP-complet; HORN-3SAT et ANTIHORN-3SAT sont tous deux en P.

Kyle Jones
la source

Je ne peux pas suivre ton exemple. L'intersection de HORN-SAT et ANTIHORN-SAT est un langage assez ennuyeux qui est définitivement en P.

Yuval Filmus

HORN-3SAT peut être défini de plusieurs façons. Une façon consiste à corriger un codage des instances HORN-3SAT - chaque chaîne code une telle instance - puis HORN-3SAT se compose des instances satisfaisables. Cet encodage est probablement différent de l'encodage que vous utiliseriez pour ANTIHORN-3SAT, il n'est donc pas clair quel est exactement le langage d'intersection - certainement pas SAT.

Yuval Filmus

Une autre possibilité consiste à définir HORN-3SAT comme le langage des instances 3SAT qui sont (i) sous forme de Horn, (ii) satisfaisables. Maintenant, l'intersection de HORN-3SAT et ANTIHORN-3SAT a un sens: elle se compose de toutes les instances de 3SAT qui sont (i) à la fois sous forme de corne et anti-corne, (ii) satisfaisables. Cela ne peut être plus facile que chacun de HORN-3SAT et ANTIHORN-3SAT.

Yuval Filmus

L_{1}

$L_1$

L_{2}

$L_2$

L_{1} \cap L_{2}

$L_1 \cap L_2$

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