les langues NP Complete sont-elles fermées dans le cadre d'opérations régulières?

8

J'ai essayé de chercher en ligne, mais je n'ai trouvé aucune déclaration définitive. Il serait logique pour moi que l'union et l'intersection de deux langues NPC produisent une langue qui n'est pas nécessairement dans NPC. Est-il également vrai que les langages des PNJ ne sont pas fermés sous le complément, la concaténation et les opérations des étoiles kleene?

user16742
la source
1
juste une note: les opérations régulières sont l'union, la concaténation et l'étoile de Kleene et non l' intersection et le complément
A.Schulz
Pourquoi pas l'intersection et le complément? Je n'ai vu aucune définition officielle des opérations régulières nulle part.
Tushar
@Tushar En effet: l'union, la concaténation et l'étoile de Kleene sont des opérations régulières, alors que l'union, l'intersection et le complément sont des opérations booléennes. Voir wikipedia .
Hendrik Jan
@Tushar: Parce que ces opérations sont utilisées pour construire des expressions régulières .
A.Schulz

Réponses:

15

Pour tous les exemples de cette réponse, je considère que l'alphabet est . Notez que les langues et sont certainement pas complètes en NP .{0,1}{0,1}

  • La classe des langages complets NP n'est pas fermée sous intersection. Pour toute NP langue -complete  , laissez et . et  sont tous deux NP- mais .LL0={0wwL}L1={1wwL}L0L1L0L1=

  • La classe des langues complètes NP n'est pas fermée sous union. Étant donné les langages NP et  de la partie précédente, laissez et . et  sont tous deux NP- complétés mais.L0L1L0=L0{1ww{0,1}}{ε}L1=L1{0ww{0,1}}{ε}L0L1L0L1={0,1}

  • La classe des langages complets NP n'est pas fermée sous concaténation. Considérez les langages NP- complets et  de la partie précédente. Puisque les deux langues contiennent  , nous avons.L0L1εL0L1L0L1={0,1}

  • La classe des langues complètes NP n'est pas fermée sous l'étoile de Kleene. Pour tout langage complet  NP , est NP complet mais.LL{0,1}(L{0,1})={0,1}

  • Si la classe des problèmes NP complets est fermée par complémentation, alors NP  =  coNP . Que cela soit vrai ou non est l'un des principaux problèmes ouverts de la théorie de la complexité.

David Richerby
la source
À l'exception du complément, les langues NP-complètes ne sont-elles pas fermées sous tous ces éléments? Ou est-ce pour P?
Ajuster
@Adjit Um. J'ai prouvé que NP n'est fermé sous aucun d'entre eux.
David Richerby
Pour votre langue spécifique. Mais je suppose que je ne vois pas comment {0, 1}*NP-complete n'est pas. Si vous prenez, par exemple, l'intersection de 2 langues NP-complètes, ne devriez-vous pas obtenir une langue NP-complète, ce qui rend NP fermé sous l'intersection?
Ajuster
{0, 1} * et le langage vide sont réguliers, donc décidables en temps polynomial et non NP-Complete. @DavidRicherby a montré qu'il existe deux langages NP-Complete dont l'intersection n'est pas NP-Complete. Cela suffit pour prouver que NPC n'est pas fermé sous intersection.
weirdev
@weirdev Non! et ne sont pas complets en NP car aucune autre langue ne se réduit à eux. Il ne suffit pas de dire qu'ils sont en P - nous ne savons pas que les langues en P ne peuvent pas être complètes en NP . Σ
David Richerby
-2

Jetez un œil aux preuves d'union, d'intersection, de concaténation et d'étoile kleene des langages NP, ici . Il semble qu'un argument similaire pourrait être avancé pour les langues NP-Complete.

Pour la notation,

  • A être un oracle qui décide un problème NP-complet connu comme 3-SAT. Voir la définition de turing réductible
  • L1 et sont des langues NP-CompleteL2
  • M1 et sont les machines qui décident de Turing et en utilisant .M2L1L2A
  • L3 estL1L2
  • M3 est une machine de turing qui décideL3

Dans le cas de l'union à partir de 1 , on peut créer une nouvelle machine qui décide en appelantM3L3M1 et M2comme sous-routines. À son tour, à chaque foisM1 ou M2 est appelé, Aest également appelé. DoncM3 décide L3 en utilisant A. Par l'argument de 1 , le temps d'exécution deM3 est en P et puisqu'il utilise A comme sous-programme, L3est NP-Complete. En d'autres termes,L3 est NP-Complete pour la même raison que L1et sont NP-Complete.L2

Le même argument peut être fait intersection et il semble que des arguments similaires pourraient être avancés pour la concaténation et l'étoile kleene.

Dans le cas du compliment, il semble probable qu'il soit difficile de prouver pour les mêmes raisons qu'il est difficile de prouver le compliment en NP.

joebloggs
la source
L'exhaustivité de NP est définie en termes de réductions multiples, pas de réductions oracle. De plus, les langages NP-complets ne sont définitivement pas fermés sous l'union ou l'intersection. S'ils sont fermés sous complément, alors NP = coNP, qui est une question ouverte majeure.
David Richerby
Dans l'article de 1971 de Stephen Cook [1] qui définit le NP-Completeness, il utilise une machine de requête qui est le même concept qu'un Oracle. Vous devriez également consulter le lien ci-dessus sur la réductibilité de turing. [1] chell.co.uk/media/product/_master/1/files/…
joebloggs
@joebloggs: Je peux voir d'après votre argument que l'union et l'intersection de deux langues NP-Complete est NP. Cependant, cela ne prouve toujours pas qu'il est NP-complet. Vous devez réduire l'union ou l'intersection de deux problèmes de décision NP-complet à un problème de décision NP-complet pour le montrer.
Tushar
@DavidRicherby: Vous dites que les langages NP-complets ne sont définitivement pas fermés sous l'union ou l'intersection. Je suis intéressé par la preuve de cela. Avez-vous des références pour cette preuve?
Tushar
2
@joebloggs: Votre argument fonctionne pour les langages NP, mais PAS pour les langages NP complets. Pour prouver qu'un langage L est Np-complet, vous devez fournir une réduction polynomiale de L à un langage NP-complet connu. Quant à la réponse de David, P est fermé sous intersection, parce que le langage vide et le langage universel sont tous deux en P (donc ils sont aussi en NP), mais ils ne sont pas NP-complets. J'espère que c'est clair!
Tushar