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

10

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 L 2 est NP-complet, au moins l'un de L 1 , L 2 est-il 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 L et un autre ensemble B en 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 : = 01L1L2L1,L2LB et L 2 : = 01 L 00 B . Cependant, je ne sais pas comment procéder après cela. L1:=01L11BL2:=01L00B

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 B NPI qui est un sous - ensemble de A . Alors B ( A B ) = A est l'ensemble NP-complet d'origine. Cependant, je ne sais pas si A B 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.ABAB(AB)=AAB

Ari
la source
1
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
1
@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
NPCPP=NP
NPCNP
2
NPNP

Réponses:

1

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
5
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
1
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
1
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
4
L1L2L1L2
3
3SATHORN3SATANTIHORN3SATHORN3SATANTIHORN3SAT